É dado um grafo ponderado com $n$ vértices. A tua tarefa é encontrar um subgrafo conexo de peso total mínimo que contenha todos os vértices com números de $1$ a $n-k$, inclusive.

Para facilitar a resolução do problema e a geração dos testes, todos os testes, exceto os exemplos, são gerados pelo seguinte algoritmo:

• O júri escolhe os inteiros $n$, $m$ e $k$.
• Todas as $\frac{n\cdot(n-1)}{2}$ arestas possíveis são consideradas por ordem aleatória.
• A aresta em consideração é adicionada ao grafo se, depois de a adicionar, ainda for possível adicionar zero ou mais das arestas seguintes e obter um grafo conexo com, no máximo, $m$ arestas no total.
• O peso de cada aresta é um inteiro escolhido uniformemente ao acaso no intervalo $[50,100]$, independentemente das outras arestas.

Entrada

A primeira linha contém três inteiros $n$ ($5 \le n \le 100$), $m$ ($2\cdot n \le m \le 10\cdot n$) e $k$ ($0 \le k \le 30$). Cada uma das $m$ linhas seguintes contém três inteiros $a_i$, $b_i$ e $w_i$ ($1 \le a_i < b_i \le n$, $50 \le w_i \le 100$), indicando que os vértices $a_i$ e $b_i$ estão ligados por uma aresta de peso $w_i$.

É garantido que o grafo não tem laços nem arestas múltiplas. Além disso, em todos os testes, exceto os exemplos, é garantido que o grafo é gerado pelo algoritmo descrito acima.

Saída

Na primeira linha, imprime um inteiro $c$, o número de arestas do subgrafo escolhido. Nas $c$ linhas seguintes, imprime as arestas escolhidas: os números dos vértices ligados por cada uma. Se existirem várias respostas possíveis, imprime qualquer uma delas.

Exemplos

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

Saída 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

Saída 2

3
5 2
5 3
1 5