Gegeben ist ein gewichteter Graph mit $n$ Knoten. Deine Aufgabe ist es, einen zusammenhängenden Teilgraphen mit minimalem Gesamtgewicht zu finden, der alle Knoten mit den Nummern von $1$ bis einschließlich $n-k$ enthält.

Damit die Aufgabe leichter zu lösen und die Tests leichter zu erzeugen sind, werden alle Tests außer den Beispielen mit dem folgenden Algorithmus erzeugt:

• Die Jury wählt die ganzen Zahlen $n$, $m$ und $k$.
• Alle $\frac{n\cdot(n-1)}{2}$ möglichen Kanten werden in zufälliger Reihenfolge betrachtet.
• Die gerade betrachtete Kante wird dem Graphen hinzugefügt, wenn es danach weiterhin möglich ist, durch Hinzufügen von null oder mehr der nachfolgenden Kanten einen zusammenhängenden Graphen mit insgesamt höchstens $m$ Kanten zu erhalten.
• Das Gewicht jeder Kante ist eine gleichverteilt zufällig aus dem Intervall $[50,100]$ gewählte ganze Zahl, unabhängig von den anderen Kanten.

Eingabe

Die erste Zeile enthält drei ganze Zahlen $n$ ($5 \le n \le 100$), $m$ ($2\cdot n \le m \le 10\cdot n$) und $k$ ($0 \le k \le 30$). Jede der nächsten $m$ Zeilen enthält drei ganze Zahlen $a_i$, $b_i$ und $w_i$ ($1 \le a_i < b_i \le n$, $50 \le w_i \le 100$). Sie bedeuten, dass die Knoten $a_i$ und $b_i$ durch eine Kante mit Gewicht $w_i$ verbunden sind.

Es ist garantiert, dass der Graph keine Schleifen und keine Mehrfachkanten hat. Außerdem ist garantiert, dass der Graph in allen Tests außer den Beispielen mit dem oben beschriebenen Algorithmus erzeugt wird.

Ausgabe

Gib in der ersten Zeile eine ganze Zahl $c$ aus, die Anzahl der Kanten im gewählten Teilgraphen. Gib in den nächsten $c$ Zeilen die gewählten Kanten aus: jeweils die Nummern der durch diese Kante verbundenen Knoten. Falls mehrere Antworten möglich sind, gib eine beliebige davon aus.

Beispiele

Eingabe 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

Ausgabe 1

1
1 2

Eingabe 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

Ausgabe 2

3
5 2
5 3
1 5