Se te da un grafo ponderado de $n$ vértices. Tu tarea es encontrar un subgrafo conexo de peso total mínimo que contenga todos los vértices con números del $1$ al $n-k$, ambos inclusive.

Para facilitar la resolución del problema y la generación de las pruebas, todas las pruebas excepto los ejemplos se generan mediante el siguiente algoritmo:

• El jurado elige los enteros $n$, $m$ y $k$.
• Se consideran las $\frac{n\cdot(n-1)}{2}$ aristas posibles en orden aleatorio.
• La arista que se está considerando se añade al grafo si, después de añadirla, todavía es posible añadir cero o más de las aristas siguientes y obtener un grafo conexo con un máximo de $m$ aristas en total.
• El peso de cada arista es un entero elegido uniformemente al azar en el intervalo $[50,100]$, independientemente de las demás aristas.

Entrada

La primera línea contiene tres enteros $n$ ($5 \le n \le 100$), $m$ ($2\cdot n \le m \le 10\cdot n$) y $k$ ($0 \le k \le 30$). Cada una de las siguientes $m$ líneas contiene tres enteros $a_i$, $b_i$ y $w_i$ ($1 \le a_i < b_i \le n$, $50 \le w_i \le 100$), que indican que los vértices $a_i$ y $b_i$ están unidos por una arista de peso $w_i$.

Se garantiza que el grafo no tiene bucles ni aristas múltiples. Además, se garantiza que en todas las pruebas excepto los ejemplos, el grafo se genera con el algoritmo descrito anteriormente.

Salida

En la primera línea, imprime un entero $c$, el número de aristas del subgrafo elegido. En las siguientes $c$ líneas, imprime las aristas elegidas: los números de los vértices unidos por cada una. Si hay varias respuestas posibles, imprime cualquiera de ellas.

Ejemplos

Entrada 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

Salida 1

1
1 2

Entrada 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

Salida 2

3
5 2
5 3
1 5