Problem D
Minimum Spanning Tree

Given an undirected connected graph with $n$ vertices and $m$ weighted edges, you can add at most $k$ more edges to the graph. If the edge you add connects vertices $u$ and $v$, then it will have a weight of $|u - v|$.

Minimize the total weight of edges in the minimum spanning tree.

Note that the graph may contain self loops or multiple edges, and it is allowed to add an edge between two vertices when there is already one or more edges between them.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case:

The first line contains three integers $n$, $m$, and $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$) indicating the number of vertices in the graph, the number of edges in the graph, and the number of edges you can add.

For the following $m$ lines, the $i$-th line contains three integers $u_i$, $v_i$, and $w_i$ ($1 \le u_i, v_i \le n$, $0 \le w_i \le 10^9$) indicating an edge connecting vertices $u_i$ and $v_i$ with weight $w_i$.

It is guaranteed that the given graph is connected. It is also guaranteed that the sum of $n$, the sum of $m$, and the sum of $k$ of all test cases will not exceed $2 \times 10^5$.

Output

For each test case:

First, output one line containing one integer $c$ ($0 \le c \le k$), indicating the number of edges you want to add.

Then output $c$ lines, where the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$), indicating that the $i$-th edge you add connects vertices $u_i$ and $v_i$, and has a weight of $|u_i - v_i|$.

Then output one line containing one integer, indicating the minimum total weight of the minimum spanning tree.

Then output one line containing $(n - 1)$ distinct integers $e_1, e_2, \cdots , e_{n - 1}$ ($1 \le e_i \le m + c$) separated by a space, indicating the indices of the edges on the minimum spanning tree. Note that $1 \le e_i \le m$ indicates an edge in the original graph, and $e_i > m$ indicates the $(e_i - m)$-th edge you add.

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

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