Ethan 的任务是为一个带权连通无向图寻找一棵最小生成树。然而，他误解了任务，找到了一棵可能不是最小的生成树。为了使他的生成树成为一棵最小生成树，你需要执行一系列边交换操作。一次边交换操作会从生成树中移除一条边，并从图中添加一条当前不在生成树中的边。在每次边交换后，这棵树必须仍然是一棵生成树。请问为了修正 Ethan 的生成树，你最少需要执行多少次边交换？

输入格式

输入的第一行包含两个整数 $n$ ($2 \le n \le 2\,000$) 和 $m$ ($n - 1 \le m \le 3\,000$)，其中 $n$ 是图中的节点数，$m$ 是图中的边数。节点编号从 $1$ 到 $n$。

接下来的 $m$ 行，每行包含三个整数 $u, v$ ($1 \le u, v \le n, u \neq v$) 和 $w$ ($1 \le w \le 10^9$)，表示一条连接节点 $u$ 和 $v$、权重为 $w$ 的边。边的编号从 $1$ 到 $m$。

保证图是连通的。输入的前 $n-1$ 条边是 Ethan 初始的生成树。该图可能不是简单图；同一对节点之间可能存在多条边。

输出格式

输出一个整数 $k$，表示将该生成树变为最小生成树所需的最少边交换次数。随后输出 $k$ 行，每行包含两个整数 $a$ 和 $b$，其中 $a$ 是要移除的边的编号，$b$ 是要添加的边的编号。如果存在多组可行的 $k$ 次边交换方案，输出其中任意一组即可。

样例

输入 1

4 4
1 2 10
2 3 3
3 4 1
1 4 4

输出 1

1
1 4