In a strange country, there are ~N~ cities numbered ~1~ to ~N~, and ~M~ roads numbered ~1~ to ~M~. The government would like to connect as many cities together as possible for the minimum cost. Every day, they will activate the current minimum spanning tree/forest.

Two cities are considered connected if they can be reached directly or indirectly from one another. A bidirectional road connects two cities and has a cost to activate.

It is worth noting that all costs are distinct, which means there is always only one way to form the minimum spanning tree/forest. However, after every day, the people of the country tend to destroy roads, and a road that was activated for the day will not be usable for the rest of eternity. Thus, the government will activate a new set of roads the day after according to the same rule. The government wants to know for each road which day in the following ~K~ days it was activated or output that the road is never activated in the ~K~ following days.

Constraints

For all subtasks:

~1 \le N \le 5 \times 10^3~

~1 \le K \le 10^4~

~0 \le M \le 3 \times 10^5~

~1 \le u_i, v_i \le N~

~1 \le w_i \le 10^9~

All edges are bidirectional.

There will be no self-loops, but there can be multiple edges running through the same pair of nodes.

Subtask 1 [30%]

~0 \le M \le 1\,000~

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains three integers ~N~, ~M~, and ~K~.

The following ~M~ lines contain three integers ~u_i~, ~v_i~, ~w_i~, meaning there is a road connecting ~u_i~ and ~v_i~ with a cost of ~w_i~ to activate.

Output Specification

Output ~M~ lines, the ~i~th line contains an integer representing which day the ~i~th road in the order of input is activated, or ~-1~ if the road is never activated in the ~K~ days.

Sample Input

3 5 2
1 2 3
1 2 1
2 3 4
2 3 6
1 3 2

Sample Output

2
1
2
-1
1

Sample Explanation

On the first day, roads ~2~ and ~5~ are activated. On the second day, roads ~1~ and ~3~ are activated. Note that road ~4~ is never activated.