โจทย์ปัญหา

ในประเทศ JOI มีเกาะอยู่ $n$ เกาะ แต่ละเกาะมีหมายเลขกำกับตั้งแต่ $1$ ถึง $n$ ปัจจุบันในประเทศ JOI กำลังดำเนินการพัฒนาโครงข่ายเส้นทางเดินเรือที่เชื่อมต่อระหว่างแต่ละเกาะ

คุณทำงานอยู่ที่ศูนย์จำหน่ายตั๋วซึ่งดูแลเรื่องตั๋วเรือ ในประเทศ JOI มีผู้คนจำนวนมากที่ต้องการเดินทางระหว่างเกาะด้วยเรือโดยเสียค่าใช้จ่ายให้ถูกที่สุดเท่าที่จะเป็นไปได้ พวกเขาจะกรอกเกาะต้นทางและเกาะปลายทางลงในใบสั่งซื้อแล้วส่งมาให้คุณ

งานของคุณคือทันทีที่ได้รับใบสั่งซื้อจากลูกค้า คุณจะต้องคำนวณค่าโดยสารที่ถูกที่สุดในบรรดาเส้นทางที่เชื่อมระหว่างเกาะต้นทางและเกาะปลายทางด้วยการต่อเรือหลายลำ แล้วแจ้งให้ลูกค้าทราบ อย่างไรก็ตาม ขึ้นอยู่กับแผนการเดินทาง อาจมีกรณีที่ไม่สามารถเดินทางด้วยเรือได้ ในกรณีนั้นจำเป็นต้องแจ้งลูกค้าว่า "ไม่สามารถเดินทางด้วยเรือได้" นอกจากนี้ ในประเทศ JOI ยังมีเรือลำใหม่ๆ ที่เชื่อมต่อระหว่างเกาะเริ่มเปิดให้บริการอย่างต่อเนื่อง และข้อมูลเหล่านั้นจะถูกแจ้งให้คุณทราบเป็นระยะ ในการตอบกลับลูกค้า คุณจะต้องคำนึงถึงข้อมูลล่าสุดเสมอ

เมื่อกำหนดใบสั่งซื้อของลูกค้าและข้อมูลการเดินเรือของเรือที่เพิ่งเริ่มเปิดให้บริการเป็นข้อมูลนำเข้า จงเขียนโปรแกรมเพื่อหาคำตอบสำหรับลูกค้า

ข้อมูลนำเข้า

บรรทัดที่ $1$ ของข้อมูลนำเข้ามีจำนวนเต็ม $2$ จำนวน คือ $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$) ซึ่งแสดงว่ามีเกาะจำนวน $n$ เกาะ และข้อมูลนำเข้าประกอบด้วย $k + 1$ บรรทัด ในบรรทัดที่ $(i + 1)$ ($1 \le i \le k$) จะมีจำนวนเต็ม $3$ หรือ $4$ จำนวนเขียนคั่นด้วยช่องว่าง

• เมื่อตัวเลขตัวแรกเป็น $0$ บรรทัดนี้จะแทนใบสั่งซื้อของลูกค้า ในบรรทัดนี้จะมีจำนวนเต็ม $3$ จำนวน คือ $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$) เขียนคั่นด้วยช่องว่าง ซึ่งหมายความว่าลูกค้าได้ส่งใบสั่งซื้อที่มีเกาะ $a$ เป็นต้นทางและเกาะ $b$ เป็นปลายทาง
• เมื่อตัวเลขตัวแรกเป็น $1$ บรรทัดนี้จะแทนข้อมูลการเดินเรือของเรือที่เพิ่งเริ่มเปิดให้บริการ ในบรรทัดนี้จะมีจำนวนเต็ม $4$ จำนวน คือ $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$) ซึ่งหมายความว่าเรือที่วิ่งไปกลับระหว่างเกาะ $c$ และเกาะ $d$ ได้เริ่มเปิดให้บริการใหม่ โดยค่าโดยสารของเรือลำนี้จากเกาะ $c$ ไปยังเกาะ $d$ และจากเกาะ $d$ ไปยังเกาะ $c$ มีค่าเท่ากับ $e$ ทั้งคู่ สำหรับใบสั่งซื้อตั้งแต่บรรทัดนี้เป็นต้นไป จะต้องนำเรือลำนี้มาพิจารณาในการตอบกลับด้วย

ในขั้นตอนเริ่มต้น ให้ถือว่ามีเรือเปิดให้บริการอยู่ $0$ ลำ ในข้อมูลนำเข้าจะมีบรรทัดที่แสดงข้อมูลการเดินเรือไม่เกิน $1000$ บรรทัด และโปรดสังเกตว่าระหว่างเกาะคู่เดียวกันอาจมีเรือเปิดให้บริการหลายลำได้

ข้อมูลส่งออก

ให้จำนวนบรรทัดที่แทนใบสั่งซื้อในข้อมูลนำเข้าเป็น $m$ ข้อมูลส่งออกประกอบด้วย $m$ บรรทัด ในบรรทัดที่ $i$ ($1 \le i \le m$) ให้เขียนจำนวนเต็มที่แทนคำตอบสำหรับใบสั่งซื้อลำดับที่ $i$ กล่าวคือ หากสามารถเดินทางระหว่างต้นทางและปลายทางของใบสั่งซื้อลำดับที่ $i$ โดยการต่อเรือหลายลำได้ ให้เขียนค่าต่ำสุดของผลรวมค่าโดยสาร หากไม่สามารถเดินทางได้ ให้เขียน $-1$

ตัวอย่างข้อมูลนำเข้าและส่งออก

ข้อมูลนำเข้าตัวอย่างที่ 1

3 8
1 3 1 10
0 2 3
1 2 3 20
1 1 2 5
0 3 2
1 1 3 7
1 2 1 9
0 2 3

ข้อมูลส่งออกตัวอย่างที่ 1

-1
15
12

ข้อมูลนำเข้าตัวอย่างที่ 2

5 16
1 1 2 343750
1 1 3 3343
1 1 4 347392
1 1 5 5497
1 2 3 123394
1 2 4 545492
1 2 5 458
1 3 4 343983
1 3 5 843468
1 4 5 15934
0 2 1
0 4 1
0 3 2
0 4 2
0 4 3
0 5 3

ข้อมูลส่งออกตัวอย่างที่ 2

5955
21431
9298
16392
24774
8840