Yana, Mino, White ja Huzz ovat parhaita ystäviä.

Eräänä päivänä valmentaja pyysi Whitea, Minoa ja Huzzia valmistelemaan harjoituskilpailun. Huzz suunnitteli kauniin hakuongelman, jonka aikavaativuus on eksponentiaalinen luvun $k$ suhteen. Hän tarkisti huolellisesti koko tehtävänannon yhtä yksityiskohtaa lukuun ottamatta: hän kirjoitti vahingossa $k \le 5 \times 10^5$ eikä $k \le 10$. Myöhemmin tämä tehtävä oli mukana harjoituskilpailussa. Raivostunut kilpailija Yana tuli Huzzin luo kysymään, miten tehtävä oikein piti ratkaista. Mutta Huzz vaikutti unohtaneen jotain, ja hänen antamansa tehtävänanto näytti hieman erilaiselta —

Sinulle annetaan suunnattu verkko, jossa on $n$ solmua ja $m$ kaarta, ja jokaiselle kaarelle $e$ on annettu kokonaislukupaino $w(e)$ väliltä $1$ ja $8$.

Polku on kaarten jono $(e_1, e_2, \dots, e_\ell)$, jolle kaaren $e_i$ loppupiste on kaaren $e_{i+1}$ alkupiste kaikilla $1 \le i < \ell$. Polun pituus on $\ell$, eli sen sisältämien kaarten lukumäärä. Huomaa, että polku voi sisältää saman kaaren useita kertoja.

Polun painojono on kaarten painojen jono $[w(e_1), w(e_2), \dots, w(e_\ell)]$. Polkuja vertaillaan niiden painojonojen leksikografisen järjestyksen mukaan.

Kaksi polkua katsotaan erillisiksi, jos ne käyttävät eri kaaria, vaikka niillä olisi sama solmujono ja painojono. Esimerkiksi jos molemmilla poluilla $(e_1, e_2)$ ja $(e_3, e_4)$ on painojono [1,2] ja molemmat kulkevat solmujen $1 \to 2 \to 3$ kautta, ne ovat silti erillisiä, kunhan $e_1 \neq e_3$ tai $e_2 \neq e_4$.

White haluaa löytää leksikografisesti $k$ pienintä polkua. Koska kokonaistuloste voi olla liian suuri, sinun tarvitsee vain tulostaa kunkin polun pituus.

Syöte

Syötteen ensimmäinen rivi sisältää kolme kokonaislukua $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$), jotka kuvaavat solmujen lukumäärää, kaarten lukumäärää ja vaadittujen polkujen lukumäärää.

Jokainen seuraavista $m$ rivistä sisältää kolme kokonaislukua $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), jotka kuvaavat suunnattua kaarta $e = (x, y)$, jonka paino on $w(e) = z$. Annettu kaarijoukko voi sisältää rinnakkaisia kaaria.

Tuloste

Tulosta $k$ riviä. Rivillä $i$ tulee olla yksi kokonaisluku: sen polun pituus, jonka painojono on leksikografisessa järjestyksessä $i$:nneksi pienin. Jos polkuja on vähemmän kuin $i$, tulosta sen sijaan $-1$.

Esimerkit

Syöte

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

Tuloste

1
1
1
2
3
4
5
6

Syöte

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

Tuloste

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

Syöte

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

Tuloste

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

Huomautus

Yksinkertaisuuden vuoksi olkoon $e_j$ syötteen $j$:s kaari.

Ensimmäisessä testitapauksessa leksikografisesti pienimmät $8$ polkua ovat:

• Polku $(e_1)$, painojono [1].
• Polku $(e_3)$, painojono [1].
• Polku $(e_5)$, painojono [1].
• Polku $(e_5, e_1)$, painojono [1,1].
• Polku $(e_5, e_1, e_4)$, painojono [1,1,2].
• Polku $(e_5, e_1, e_4, e_5)$, painojono [1,1,2,1].
• Polku $(e_5, e_1, e_4, e_5, e_1)$, painojono [1,1,2,1,1].
• Polku $(e_5, e_1, e_4, e_5, e_1, e_4)$, painojono [1,1,2,1,1,2].