Yana, Mino, White, dan Huzz adalah sahabat karib.

Suatu hari, pelatih meminta White, Mino, dan Huzz untuk menyiapkan kontes simulasi. Huzz merancang soal pencarian yang indah yang kompleksitasnya eksponensial terhadap $k$. Ia memeriksa seluruh deskripsi soal dengan cermat, kecuali satu detail: ia tidak sengaja menulis $k \le 5 \times 10^5$ alih-alih $k \le 10$. Kemudian, soal ini muncul dalam kontes simulasi. Peserta yang marah, Yana, mendatangi Huzz dan menanyakan bagaimana soal tersebut seharusnya diselesaikan. Namun ia tampaknya telah melupakan sesuatu, dan deskripsi soal yang ia berikan terlihat sedikit berbeda —

Anda diberikan sebuah graf berarah dengan $n$ simpul dan $m$ sisi, di mana setiap sisi $e$ diberi bobot bilangan bulat $w(e)$ antara $1$ dan $8$.

Sebuah lintasan adalah barisan sisi $(e_1, e_2, \dots, e_\ell)$ sedemikian sehingga titik akhir dari $e_i$ adalah titik awal dari $e_{i+1}$ untuk semua $1 \le i < \ell$. Panjang lintasan adalah $\ell$, yaitu banyaknya sisi yang dikandungnya. Perhatikan bahwa sebuah lintasan boleh memuat sisi yang sama berkali-kali.

Barisan bobot dari lintasan adalah barisan bobot sisi $[w(e_1), w(e_2), \dots, w(e_\ell)]$. Lintasan-lintasan dibandingkan berdasarkan urutan leksikografis dari barisan bobotnya.

Dua lintasan dianggap berbeda selama keduanya menggunakan sisi yang berbeda, meskipun keduanya memiliki barisan simpul dan barisan bobot yang sama. Sebagai contoh, jika kedua lintasan $(e_1, e_2)$ dan $(e_3, e_4)$ memiliki barisan bobot [1,2], dan keduanya melewati simpul $1 \to 2 \to 3$, keduanya tetap berbeda selama $e_1 \neq e_3$ atau $e_2 \neq e_4$.

White ingin mencari $k$ lintasan terkecil secara leksikografis. Karena total keluaran mungkin terlalu besar, Anda hanya perlu mengeluarkan panjang dari setiap lintasan.

Masukan

Baris pertama masukan berisi tiga bilangan bulat $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$), yang menyatakan banyaknya simpul, banyaknya sisi, dan banyaknya lintasan yang diminta.

Masing-masing dari $m$ baris berikutnya berisi tiga bilangan bulat $x, y, z$ ($1 \le x, y \le n, 1 \le z \le 8, x \neq y$), yang menyatakan sebuah sisi berarah $e = (x, y)$ dengan bobot $w(e) = z$. Himpunan sisi yang diberikan mungkin memuat sisi ganda.

Keluaran

Cetak $k$ baris. Baris ke-$i$ harus berisi sebuah bilangan bulat tunggal, yaitu panjang lintasan yang bobotnya terkecil ke-$i$ dalam urutan leksikografis. Jika terdapat kurang dari $i$ lintasan, cetak $-1$ sebagai gantinya.

Contoh

Masukan

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

Keluaran

1
1
1
2
3
4
5
6

Masukan

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

Keluaran

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

Masukan

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

Keluaran

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

Catatan

Untuk penyederhanaan, misalkan $e_j$ menyatakan sisi masukan ke-$j$.

Untuk kasus uji pertama, $8$ lintasan terkecil secara leksikografis adalah:

• Lintasan $(e_1)$, barisan bobot [1].
• Lintasan $(e_3)$, barisan bobot [1].
• Lintasan $(e_5)$, barisan bobot [1].
• Lintasan $(e_5, e_1)$, barisan bobot [1,1].
• Lintasan $(e_5, e_1, e_4)$, barisan bobot [1,1,2].
• Lintasan $(e_5, e_1, e_4, e_5)$, barisan bobot [1,1,2,1].
• Lintasan $(e_5, e_1, e_4, e_5, e_1)$, barisan bobot [1,1,2,1,1].
• Lintasan $(e_5, e_1, e_4, e_5, e_1, e_4)$, barisan bobot [1,1,2,1,1,2].