시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB41133.333%

문제

You are given a weighted graph on $n$ vertices. You should find a connected subgraph of minimal weight, which contains all vet rices with numbers from $1$ to $n - k$.

To make problem easier to solve, and tests easier to generate, all tests are generated using following algorithm:

  • Integers $n$, $m$, $k$ are chosen.
  • All $\frac{n\cdot(n-1)}{2}$ possible edges are shuffled in random order
  • Next edge is added to graph if after it is add, it's possible to add some more edges to make graph connected with $m$ edges total.
  • For each edge weight is generated uniformly on segment $[50, 100]$ independent from other edges.

입력

In first line there are three integers $n$ ($5 \le n \le 100$), $m$ ($2\cdot n \le m \le 10\cdot n$), $k$ ($0 \le k \le 30$). On next $m$ lines there are triples of integers $a_i b_i w_i$ ($1 \le a_i < b_i \le n$, $50 \le w_i \le 100$), each of them means, that vertices $a_i$ и $b_i$ are connected by edge of weight $w_i$.

It's guaranteed, that graph have no loops, multiple edges, and in all tests, except samples it's generated by algorithm described above.

출력

In first line, print one integer $c$ --- number of edges in chosen subgraph. In next $c$ lines print chosen edges.

예제 입력 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

예제 출력 1

1
1 2

예제 입력 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

예제 출력 2

3
5 2
5 3
1 5