Yana, Mino, White og Huzz eru bestu vinir.

Dag einn bað þjálfarinn White, Mino og Huzz um að undirbúa æfingakeppni. Huzz hannaði fallegt leitarverkefni þar sem tímaflækjan er veldisvísisfall af $k$. Hann fór vandlega yfir alla verkefnalýsinguna, nema eitt smáatriði: hann skrifaði óvart $k \le 5 \times 10^5$ í stað $k \le 10$. Síðar birtist þetta verkefni í æfingakeppni. Reiði keppandinn, Yana, kom til Huzz og spurði hvernig ætti eiginlega að leysa verkefnið. En hann virtist hafa gleymt einhverju og verkefnalýsingin sem hann lét í té leit örlítið öðruvísi út —

Gefið er stefnt net með $n$ hnútum og $m$ leggjum, þar sem hverjum legg $e$ er úthlutað heiltöluvigt $w(e)$ á milli $1$ og $8$.

Vegur er runa af leggjum $(e_1, e_2, \dots, e_\ell)$ þannig að endapunktur $e_i$ er upphafspunktur $e_{i+1}$ fyrir öll $1 \le i < \ell$. Lengd vegarins er $\ell$, fjöldi leggja sem hann inniheldur. Athugið að vegur getur innihaldið sama legginn margoft.

Vigtruna vegarins er runa leggjavigtanna $[w(e_1), w(e_2), \dots, w(e_\ell)]$. Vegir eru bornir saman í stafrófsröð (lexicographical order) vigtruna sinna.

Tveir vegir teljast ólíkir svo lengi sem þeir nota ólíka leggi, jafnvel þótt þeir deili sömu hnútarunu og vigtrunu. Til dæmis, ef báðir vegirnir $(e_1, e_2)$ og $(e_3, e_4)$ hafa vigtrununa [1,2], og báðir fara um hnútana $1 \to 2 \to 3$, þá eru þeir samt ólíkir svo lengi sem $e_1 \neq e_3$ eða $e_2 \neq e_4$.

White vill finna $k$ minnstu vegina í stafrófsröð. Þar sem heildarúttakið gæti verið of stórt þarftu aðeins að skrifa út lengd hvers vegar.

Inntak

Fyrsta lína inntaksins inniheldur þrjár heiltölur $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$), sem tákna fjölda hnúta, fjölda leggja og umbeðinn fjölda vega.

Hver af næstu $m$ línum inniheldur þrjár heiltölur $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), sem tákna stefndan legg $e = (x, y)$ með vigt $w(e) = z$. Gefna leggjamengið getur innihaldið margfalda leggi.

Úttak

Prentaðu $k$ línur. $i$-ta línan á að innihalda eina heiltölu, lengd vegarins sem hefur $i$-tu minnstu vigtina í stafrófsröð. Ef það eru færri en $i$ vegir skaltu prenta $-1$ í staðinn.

Dæmi

Inntak

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

Úttak

1
1
1
2
3
4
5
6

Inntak

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

Úttak

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

Inntak

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

Úttak

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

Athugasemd

Til einföldunar látum við $e_j$ tákna $j$-ta legginn í inntakinu.

Í fyrsta prófunartilvikinu eru $8$ minnstu vegirnir í stafrófsröð:

• Vegur $(e_1)$, vigtruna [1].
• Vegur $(e_3)$, vigtruna [1].
• Vegur $(e_5)$, vigtruna [1].
• Vegur $(e_5, e_1)$, vigtruna [1,1].
• Vegur $(e_5, e_1, e_4)$, vigtruna [1,1,2].
• Vegur $(e_5, e_1, e_4, e_5)$, vigtruna [1,1,2,1].
• Vegur $(e_5, e_1, e_4, e_5, e_1)$, vigtruna [1,1,2,1,1].
• Vegur $(e_5, e_1, e_4, e_5, e_1, e_4)$, vigtruna [1,1,2,1,1,2].