On vous donne un graphe pondéré à $n$ sommets. Votre tâche consiste à trouver un sous-graphe connexe de poids total minimal contenant tous les sommets dont les numéros vont de $1$ à $n-k$ inclus.

Pour faciliter la résolution du problème et la génération des tests, tous les tests, à l’exception des exemples, sont générés par l’algorithme suivant :

• Le jury choisit les entiers $n$, $m$ et $k$.
• Toutes les $\frac{n\cdot(n-1)}{2}$ arêtes possibles sont examinées dans un ordre aléatoire.
• L’arête en cours d’examen est ajoutée au graphe si, après son ajout, il est encore possible d’ajouter zéro ou plusieurs des arêtes suivantes et d’obtenir un graphe connexe comportant au plus $m$ arêtes au total.
• Pour chaque arête, son poids est un entier choisi uniformément au hasard dans l’intervalle $[50,100]$, indépendamment des autres arêtes.

Entrée

La première ligne contient trois entiers $n$ ($5 \le n \le 100$), $m$ ($2\cdot n \le m \le 10\cdot n$) et $k$ ($0 \le k \le 30$). Chacune des $m$ lignes suivantes contient trois entiers $a_i$, $b_i$ et $w_i$ ($1 \le a_i < b_i \le n$, $50 \le w_i \le 100$), indiquant que les sommets $a_i$ et $b_i$ sont reliés par une arête de poids $w_i$.

Il est garanti que le graphe ne contient ni boucle ni arêtes multiples. De plus, dans tous les tests sauf les exemples, le graphe est garanti être généré par l’algorithme décrit ci-dessus.

Sortie

Sur la première ligne, affichez un entier $c$, le nombre d’arêtes du sous-graphe choisi. Sur les $c$ lignes suivantes, affichez les arêtes choisies : les numéros des sommets reliés par chacune d’elles. S’il existe plusieurs réponses possibles, affichez n’importe laquelle.

Exemples

Entrée 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

Sortie 1

1
1 2

Entrée 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

Sortie 2

3
5 2
5 3
1 5