给定一个包含 $n$ 个顶点和 $m$ 条带权边的无向连通图，你可以向图中最多添加 $k$ 条边。如果你添加的边连接了顶点 $u$ 和 $v$，则该边的权重为 $|u - v|$。请最小化最小生成树的总权重。

注意，原图可能包含自环或重边，且允许在两个顶点之间添加边，即使它们之间已经存在一条或多条边。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $n, m$ 和 $k$ ($2 \le n \le 2 \times 10^5, n - 1 \le m \le 2 \times 10^5, 0 \le k \le 2 \times 10^5$)，分别表示图中的顶点数、边数以及你可以添加的边数。

接下来的 $m$ 行，第 $i$ 行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, 0 \le w_i \le 10^9$)，表示一条连接顶点 $u_i$ 和 $v_i$、权重为 $w_i$ 的边。

保证给定的图是连通的。同时保证所有测试数据的 $n$ 之和、 $m$ 之和以及 $k$ 之和均不超过 $2 \times 10^5$。

输出格式

对于每组测试数据：

首先，输出一行包含一个整数 $c$ ($0 \le c \le k$)，表示你想要添加的边数。

然后输出 $c$ 行，其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示你添加的第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，其权重为 $|u_i - v_i|$。

接着输出一行包含一个整数，表示最小生成树的最小总权重。

最后输出一行包含 $(n - 1)$ 个不同的整数 $e_1, e_2, \dots, e_{n-1}$ ($1 \le e_i \le m + c$)，用空格分隔，表示最小生成树中边的编号。注意，$1 \le e_i \le m$ 表示原图中的边，而 $e_i > m$ 表示你添加的第 $(e_i - m)$ 条边。

样例

样例输入 1

3
5 6 2
1 2 3
2 3 5
1 4 7
4 2 4
5 4 8
3 5 1
4 5 100
1 2 2
2 3 0
2 4 0
4 1 1
3 4 3
3 2 0
1 2 100
2 3 100

样例输出 1

2
2 3
3 4
6
8 1 6 7
0
1
2 3 4
0
200
1 2