For a given graph G with N vertices and M edges, where $w_i$ denotes the weight of the i-th edge, the goal is to remove at most K edges from G producing a new graph G, in such a way that G is connected and the weight of minimum spanning tree of G is maximized.

Input format

In the first line, there are three space separated integer N, M and K, denoting respectively the number of vertices, the number edges, and the maximum allowed number of edges to be removed from the graph. After that, M lines follow. In the i-th of them there are three space-separated integers $u_i$, $v_i$, $w_i$ denoting that the i-th edge in the graph connects vertices $u_i$ and $v_i$, and it has weight $w_i$.

Output format

In the first line, print a single integer X, denoting the number of edges in your answer. In the second line, print X space-separated integers denoting the indices of the edges remaining in the graph. Just for clarification, the first edge given in the input has the index 1 and the last one has the index M.

Constraints

$N = 5000$
$5 \cdot 10^4 \leq M \leq 10^5$
$100 \leq K \leq 5000$
$1 \leq w_i \leq 10^6$
$1 \leq u_i, v_i \leq N$
the input graph is connected

Scoring

The answer is considered incorrect if:

• The set of edges denoted by indices in the output is not a subset of edges given in the input.
• The same edge appears multiple times in the output.
• More than K edges were removed.
• The resulting graph after removing the edges is not connected.

Otherwise, for a single test file its absolute score is:

$\frac{MST(G')}{MST(G}$

where $MST(G)$ is the weight of minimum spanning tree of G.

The total absolute score of a submission is the sum of absolute scores across all test files. In this problem, scoring is set to relative, which means that the final score for a problem is your absolute score divided by the score of the best solution submitted by any participant. The objective is to maximize the total absolute score.

After the contest, new test files will be generated with the same method described below, and all submissions will be rejudged on these new test files.

Test generation

• M is generated uniformly at random from range $[5 \cdot 10^4, 10^5]$
• K is generated uniformly at random from one of ranges: $[100,500]$, $[1000, 5000]$, and all these ranges are used equal number of times among test files
• G is generated using this graph generation method
• $w_i$ for each i is generated uniformly at random from a range $[1, 10^6]$ and independently of other weights.