Dany jest graf ważony o $n$ wierzchołkach. Twoim zadaniem jest znaleźć spójny podgraf o minimalnej sumie wag, zawierający wszystkie wierzchołki o numerach od $1$ do $n-k$ włącznie.

Aby ułatwić rozwiązanie zadania i generowanie testów, wszystkie testy poza przykładami są generowane następującym algorytmem:

• Jury wybiera liczby całkowite $n$, $m$ i $k$.
• Wszystkie $\frac{n\cdot(n-1)}{2}$ możliwych krawędzi są rozpatrywane w losowej kolejności.
• Rozpatrywana krawędź jest dodawana do grafu, jeśli po jej dodaniu nadal można dodać zero lub więcej spośród kolejnych krawędzi i otrzymać spójny graf o łącznie co najwyżej $m$ krawędziach.
• Waga każdej krawędzi jest liczbą całkowitą losowaną jednostajnie z przedziału $[50,100]$, niezależnie od pozostałych krawędzi.

Wejście

Pierwszy wiersz zawiera trzy liczby całkowite $n$ ($5 \le n \le 100$), $m$ ($2\cdot n \le m \le 10\cdot n$) i $k$ ($0 \le k \le 30$). Każdy z następnych $m$ wierszy zawiera trzy liczby całkowite $a_i$, $b_i$ i $w_i$ ($1 \le a_i < b_i \le n$, $50 \le w_i \le 100$), oznaczające, że wierzchołki $a_i$ i $b_i$ łączy krawędź o wadze $w_i$.

Gwarantuje się, że graf nie ma pętli ani krawędzi wielokrotnych. Ponadto we wszystkich testach poza przykładami graf jest generowany opisanym wyżej algorytmem.

Wyjście

W pierwszym wierszu wypisz jedną liczbę całkowitą $c$, liczbę krawędzi wybranego podgrafu. W kolejnych $c$ wierszach wypisz wybrane krawędzie: numery wierzchołków połączonych każdą z nich. Jeśli istnieje kilka poprawnych odpowiedzi, wypisz dowolną z nich.

Przykład

Wejście 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

Wyjście 1

1
1 2

Wejście 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

Wyjście 2

3
5 2
5 3
1 5