给定一张有 $n$ 个顶点的带权图。你的任务是找出一个总权值最小的连通子图，使其包含编号从 $1$ 到 $n-k$ 的所有顶点（包括两端）。

为了让问题更容易求解、测试数据更容易生成，除样例外的所有测试数据均由以下算法生成：

• 由出题人选择整数 $n$、$m$ 和 $k$。
• 以随机顺序考虑全部 $\frac{n\cdot(n-1)}{2}$ 条可能的边。
• 考虑一条边时，如果加入它后，仍能通过加入后续边中的零条或多条，得到一张总边数不超过 $m$ 的连通图，就将其加入图中。
• 每条边的权值均从区间 $[50,100]$ 中独立、均匀随机地选取一个整数。

输入格式

第一行包含三个整数 $n$（$5 \le n \le 100$）、$m$（$2\cdot n \le m \le 10\cdot n$）和 $k$（$0 \le k \le 30$）。接下来 $m$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $w_i$（$1 \le a_i < b_i \le n$，$50 \le w_i \le 100$），表示顶点 $a_i$ 和 $b_i$ 之间有一条权值为 $w_i$ 的边。

保证图中没有自环或重边。此外，保证除样例外的所有测试数据中的图均由上述算法生成。

输出格式

第一行输出一个整数 $c$，表示所选子图的边数。接下来 $c$ 行输出所选的边：每行输出一条边连接的两个顶点的编号。如果存在多个答案，输出其中任意一个。

样例

输入格式 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