Problem Statement

You are given a simple connected undirected graph $G$ with $N$ vertices and $M$ edges. Edge $i$ connects vertices $a_i$ and $b_i$, and has weight $c_i$. Here, each edge's weight is $0$ or $1$.

You are given a non-negative integer $K$. Determine whether there exists a spanning tree of $G$ such that the sum of the weights of the edges composing the spanning tree is exactly $K$, and if one exists, find one.

You are given $T$ test cases; solve each of them.

Constraints

• $1 \le T \le 10^5$
• $2 \le N \le 2\times 10^5$
• $N-1 \le M \le \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right)$
• $0 \le K \le N-1$
• $1 \le a_i,b_i \le N$
• $c_i=0$ or $c_i=1$.
• The graph $G$ is simple and connected.
• The sum of $N$ over all test cases is at most $2\times 10^5$.
• The sum of $M$ over all test cases is at most $2\times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each case is given in the following format:

N M K
a_1 b_1 c_1
a_2 b_2 c_2
\vdots
a_M b_M c_M

Output

Output $T$ lines. The $i$-th line should contain the answer for $\text{case}_i$.

If there is no spanning tree satisfying the condition, output -1.

Otherwise, let $x_1,x_2,\cdots,x_{N-1}$ be the numbers of the edges composing a spanning tree for that case, and output them in the following format:

x_1 x_2 \cdots x_{N-1}

$x_1,x_2,\cdots,x_{N-1}$ can be in any order. The edge numbers correspond to the input order within each case. If multiple solutions exist, any of them is accepted.