Diberikan sebuah graf berbobot dengan $n$ simpul. Tugasmu adalah mencari subgraf terhubung dengan jumlah bobot minimum yang memuat semua simpul bernomor $1$ sampai $n-k$, termasuk kedua batasnya.

Agar soal lebih mudah diselesaikan dan kasus uji lebih mudah dibuat, semua kasus uji selain contoh dibuat dengan algoritma berikut:

• Juri memilih bilangan bulat $n$, $m$, dan $k$.
• Semua $\frac{n\cdot(n-1)}{2}$ sisi yang mungkin dipertimbangkan dalam urutan acak.
• Sisi yang sedang dipertimbangkan ditambahkan ke graf jika, setelah ditambahkan, masih mungkin menambahkan nol atau lebih sisi berikutnya untuk memperoleh graf terhubung dengan paling banyak $m$ sisi secara keseluruhan.
• Untuk setiap sisi, bobotnya adalah bilangan bulat yang dipilih secara acak seragam dari interval $[50,100]$, secara independen dari sisi lain.

Masukan

Baris pertama berisi tiga bilangan bulat $n$ ($5 \le n \le 100$), $m$ ($2\cdot n \le m \le 10\cdot n$), dan $k$ ($0 \le k \le 30$). Masing-masing dari $m$ baris berikutnya berisi tiga bilangan bulat $a_i$, $b_i$, dan $w_i$ ($1 \le a_i < b_i \le n$, $50 \le w_i \le 100$), yang berarti simpul $a_i$ dan $b_i$ dihubungkan oleh sisi berbobot $w_i$.

Dijamin graf tidak memiliki gelang maupun sisi ganda. Selain itu, dijamin bahwa dalam semua kasus uji selain contoh, graf dibuat menggunakan algoritma yang dijelaskan di atas.

Keluaran

Pada baris pertama, cetak satu bilangan bulat $c$, yaitu banyaknya sisi pada subgraf yang dipilih. Pada $c$ baris berikutnya, cetak sisi-sisi yang dipilih: nomor simpul yang dihubungkan oleh setiap sisi. Jika ada beberapa jawaban yang mungkin, cetak salah satunya.

Contoh

Masukan 1

5 10 3
1 2 50
1 3 51
1 4 52
1 5 53
2 3 54
2 4 55
2 5 56
3 4 57
3 5 58
4 5 59

Keluaran 1

1
1 2

Masukan 2

5 10 2
1 2 100
1 3 100
1 4 57
1 5 56
2 3 100
2 4 54
2 5 53
3 4 52
3 5 51
4 5 50

Keluaran 2

3
5 2
5 3
1 5