Translation for 2015 JOI Inheritance

inheritance.md

Translation credit to Kaz Nakao

In the country of IOI, there was a railway mogul JOI that owned all of the railroads.
However, JOI has passed away and the railways he owns are to be distributed as a split inheritance.

In IOI, there are $N$ cities and there are $M$ railroads that connect the cities.
The cities are numbered $1$ to $N$, and the railroads are numbered $1$ to $M$.
A railroad $i$ runs between city $A_i$ and $B_i$ in both directions and generates a distinct profit of $C$ yen.
There may be several lines between the same two cities.

The railroads will be divided among the $K$ number of children that JOI has.
Each child is given a number from $1$ to $K$ in order of their age, with the oldest child being number $1$.
Each child will receive some number of railroads out of the total $M$ railroads (possibly receiving 0).
First, child 1 will choose a set of railroads to inherit from the set of M railroads.
Next, child 2 will choose anohter set of railroads to inherit from the remaining number of railroads.
Following the above pattern, the $K$ children decide which railroads to inherit.

However, there are a couple of rules about how the children will choose their railroads.

1. A child won't choose a railroad that has already been chosen. For example, if the first child chooses railroad $i$, the second child wouldn't be able to choose railroad $i$ anymore.
2. A child won't choose railroads that form a "cycle". A "cycle" is formed when you can start at a city and can get back to it using each edge in a distinct set of edges once.
3. As all the children are as greedy as their father, they will always choose the set of railroads that yield the optimal profit. It is guaranteed that there is only one inheritance arrangement that meets the above rules.

If a railroad is not chosen by any child, it becoms publicly owned.

Given the railroads and the children, determine which child will choose which railroads.

Input

The first line contains 3 space-separated integers $N$, $M$, and $K$, which are the number of cities, railways, and children respectively.
The following $M$ lines contain the space-separated integers $A_i$, $B_i$, and $C_i$, indicating that there is a railway connecting $A_i$ and $B_i$ that generates $C_i$ yen.

Output

The output should consist of $M$ lines.
Line $i$ should contain the number of the child that receives the $i$ th railway.
If no child owns the railway, output 0 instead.

Constraints

$2 \leq N \leq 1000$
$1 \leq M \leq 300000$
$1 \leq K \leq 10000$
$1 \leq A_i, B_i \leq N (1 \leq i \leq M)$
$A_i \neq B_i (1 \leq i \leq M)$
$1 \leq C_i \leq 1000000000$
$C_i \neq C_j (1 \leq i < j \leq M)$

Example Input 1

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

Example Output 1

1
0
2
1
2

Example Output 1 Explanation

The first child chooses railroads 1 and 4. These two railroads yield a total profit of 3 + 6 = 9 yen, which is the optimal profit. Note that he cannot choose railroads 3 and 4, because these two would form a cycle.

The second child chooses railroads 3 and 5 among the resulting railroads (2, 3, and 5). These two railroads yield a total profit of 4 + 2 = 6 yen, which is the most profit they can get.

Railroad 2 is not chosen, and thus becomes publicly owned.

Example Input 2

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

Example Output 2

4
3
2
1
2
1