给定一个包含 $N$ 个节点和 $M$ 条边的简单连通无向加权图 $G$。每个节点的编号为 $1$ 到 $N$。

图 $G$ 的生成树是 $G$ 的一个子图，它是一棵树且连接了 $G$ 的所有顶点。树的直径是指树中任意两个节点之间路径长度的最大值。$G$ 的最小直径生成树是指直径最小的生成树。

编写一个程序，求出任意一棵最小直径生成树。

输入格式

第一行包含两个整数 $N$ ($2 \le N \le 500$) 和 $M$ ($N - 1 \le M \le \frac{N(N-1)}{2}$)。

接下来 $M$ 行：第 $i$ ($1 \le i \le M$) 行包含三个空格分隔的整数 $u_i$、$v_i$ 和 $l_i$ ($1 \le u_i, v_i \le N, 1 \le l_i \le 10^9$)；描述了一条连接顶点 $u_i$ 和顶点 $v_i$、长度为 $l_i$ 的双向边。

保证给定的图没有自环或重边，且图是连通的。

输出格式

第一行输出 $G$ 的最小直径生成树的直径。

接下来的 $N - 1$ 行，输出最小直径生成树中边的描述。第 $j$ ($1 \le j \le N - 1$) 行应包含两个空格分隔的整数 $x_j$ 和 $y_j$ ($1 \le x_j, y_j \le N$)；描述了一条连接顶点 $x_j$ 和 $y_j$ 的双向边。

如果有多种可能的答案，输出其中任意一个即可。

样例

输入 1

3 3
1 2 1
2 3 1
3 1 1

输出 1

2
1 2
3 1

输入 2

6 7
1 2 10
2 3 20
1 3 30
3 4 1000
4 5 30
5 6 20
4 6 10

输出 2

1060
3 4
6 4
5 6
2 3
1 2