Yana, Mino, White และ Huzz เป็นเพื่อนสนิทกัน

วันหนึ่ง โค้ชขอให้ White, Mino และ Huzz เตรียมการแข่งขันจำลอง Huzz ได้ออกแบบโจทย์การค้นหาที่งดงามซึ่งมีความซับซ้อนเป็นฟังก์ชันเอกซ์โพเนนเชียลเทียบกับ $k$ เขาตรวจสอบโจทย์ทั้งหมดอย่างละเอียด ยกเว้นรายละเอียดเดียวคือ เขาเผลอเขียน $k \le 5 \times 10^5$ แทนที่จะเป็น $k \le 10$ ต่อมาโจทย์ข้อนี้ปรากฏในการแข่งขันจำลอง ผู้เข้าแข่งขันที่กำลังโกรธเกรี้ยวอย่าง Yana จึงมาหา Huzz เพื่อถามว่าโจทย์ข้อนี้ควรจะแก้อย่างไร แต่ดูเหมือนว่าเขาจะลืมอะไรบางอย่างไป และโจทย์ที่เขาให้มานั้นดูแตกต่างออกไปเล็กน้อย —

คุณได้รับกราฟระบุทิศทางที่มี $n$ จุดยอดและ $m$ เส้นเชื่อม โดยแต่ละเส้นเชื่อม $e$ จะถูกกำหนดน้ำหนักที่เป็นจำนวนเต็ม $w(e)$ ระหว่าง $1$ ถึง $8$

วิถี (path) คือลำดับของเส้นเชื่อม $(e_1, e_2, \dots, e_\ell)$ ที่จุดปลายของ $e_i$ เป็นจุดเริ่มต้นของ $e_{i+1}$ สำหรับทุก $1 \le i < \ell$ ความยาวของวิถีคือ $\ell$ ซึ่งคือจำนวนเส้นเชื่อมที่อยู่ในวิถีนั้น สังเกตว่าวิถีหนึ่งอาจมีเส้นเชื่อมเดียวกันหลายครั้งได้

ลำดับน้ำหนักของวิถีคือลำดับของน้ำหนักเส้นเชื่อม $[w(e_1), w(e_2), \dots, w(e_\ell)]$ การเปรียบเทียบวิถีจะเปรียบเทียบตามลำดับพจนานุกรมของลำดับน้ำหนักของวิถีเหล่านั้น

วิถีสองวิถีจะถือว่าแตกต่างกันตราบใดที่ใช้เส้นเชื่อมต่างกัน แม้ว่าจะมีลำดับจุดยอดและลำดับน้ำหนักเหมือนกันก็ตาม ตัวอย่างเช่น หากทั้งวิถี $(e_1, e_2)$ และ $(e_3, e_4)$ มีลำดับน้ำหนักเป็น [1,2] และทั้งคู่ผ่านจุดยอด $1 \to 2 \to 3$ ทั้งสองวิถีก็ยังคงแตกต่างกันตราบใดที่ $e_1 \neq e_3$ หรือ $e_2 \neq e_4$

White ต้องการหาวิถี $k$ อันดับแรกที่มีลำดับพจนานุกรมน้อยที่สุด เนื่องจากข้อมูลส่งออกทั้งหมดอาจมีขนาดใหญ่เกินไป คุณจึงต้องแสดงเฉพาะความยาวของแต่ละวิถีเท่านั้น

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

บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มสามจำนวน $n, m, k$ ($2 \le n \le 5 \times 10^5, 1 \le m \le 5 \times 10^5, 1 \le k \le 5 \times 10^5$) แทนจำนวนจุดยอด จำนวนเส้นเชื่อม และจำนวนวิถีที่ต้องการ

แต่ละบรรทัดในอีก $m$ บรรทัดถัดไปประกอบด้วยจำนวนเต็มสามจำนวน $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$) แทนเส้นเชื่อมระบุทิศทาง $e = (x, y)$ ที่มีน้ำหนัก $w(e) = z$ เซตของเส้นเชื่อมที่กำหนดอาจมีเส้นเชื่อมขนาน (multiple edges)

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

พิมพ์ $k$ บรรทัด บรรทัดที่ $i$ ควรมีจำนวนเต็มเพียงตัวเดียว คือความยาวของวิถีที่มีลำดับน้ำหนักน้อยเป็นอันดับที่ $i$ ตามลำดับพจนานุกรม หากมีวิถีน้อยกว่า $i$ วิถี ให้พิมพ์ $-1$ แทน

ตัวอย่าง

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

5 5 8
2 1 1
3 1 2
4 1 1
1 5 2
5 2 1

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

1
1
1
2
3
4
5
6

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

3 4 10
1 2 1
1 2 1
2 3 2
2 3 3

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

1
1
2
2
2
2
1
1
-1
-1

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

6 5 15
1 2 3
2 3 5
3 4 2
3 5 1
5 6 4

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

1
2
1
1
2
3
4
3
1
1
2
3
2
-1
-1

หมายเหตุ

เพื่อความง่าย ให้ $e_j$ แทนเส้นเชื่อมลำดับที่ $j$ ในข้อมูลนำเข้า

สำหรับชุดทดสอบแรก วิถี $8$ อันดับแรกที่มีลำดับพจนานุกรมน้อยที่สุดคือ:

• วิถี $(e_1)$, ลำดับน้ำหนัก [1].
• วิถี $(e_3)$, ลำดับน้ำหนัก [1].
• วิถี $(e_5)$, ลำดับน้ำหนัก [1].
• วิถี $(e_5, e_1)$, ลำดับน้ำหนัก [1,1].
• วิถี $(e_5, e_1, e_4)$, ลำดับน้ำหนัก [1,1,2].
• วิถี $(e_5, e_1, e_4, e_5)$, ลำดับน้ำหนัก [1,1,2,1].
• วิถี $(e_5, e_1, e_4, e_5, e_1)$, ลำดับน้ำหนัก [1,1,2,1,1].
• วิถี $(e_5, e_1, e_4, e_5, e_1, e_4)$, ลำดับน้ำหนัก [1,1,2,1,1,2].