| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 4 | 1 | 1 | 33.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:
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.
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 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
3 5 2 5 3 1 5