Inheritance (Translated)

JOI Spring Training Camp 2014/15
Original Statement / Submission Site

Problem Statement

Mr. JOI, a tycoon who owned all the railways in the country of IOI, has passed away. According to his will, the railways will be inherited and divided among his children.

There are N cities and M railways connecting them in IOI. Railway i connects cities Ai and Bi bidirectionally and generates an annual income of Ci yen. The income values C1, ..., CM are all distinct. Multiple railways may connect the same pair of cities.

His will specifies the inheritance as follows:

• The M railways will be inherited by K children, numbered from 1 (oldest) to K (youngest).
• Each child may inherit zero or more of the M railways.
• First, child 1 chooses his share from the M railways. Then, from the remaining railways, child 2 chooses his share, and so on, until all K children have chosen.
• Each child cannot choose railways that have already been chosen by older siblings.
• Each child cannot choose a set of railways that form a cycle. That is, if one can leave a city by using distinct railways i1, i2, ..., im and return to the same city, then no child can inherit all of railways i1, i2, ..., im by himself.
• Railways not inherited by anyone will be donated to the country IOI.

Each child, being greedy like their father, chooses their share to maximize the total annual income. We guarantee that the optimal selection (maximum total income without forming cycles) is unique for each child.

Task

Given the railway information and number of children, write a program to determine which child inherits each railway (or 0 if it is donated to the country).

Input

Input is given as follows:

• The first line contains three integers N, M, K – number of cities, railways, and children, respectively.
• The next M lines each contain three integers Ai, Bi, Ci – railway i connects cities Ai and Bi, and has annual income Ci.

Output

Output M lines. The i-th line contains the number of the child who inherits railway i, or 0 if it is donated to the country.

Constraints

• 2 ≤ N ≤ 1,000
• 1 ≤ M ≤ 300,000
• 1 ≤ K ≤ 10,000
• 1 ≤ Ai, Bi ≤ N (1 ≤ i ≤ M)
• Ai ≠ Bi (1 ≤ i ≤ M)
• 1 ≤ Ci ≤ 1,000,000,000 (1 ≤ i ≤ M)
• Ci ≠ Cj for any different i, j.

Subtasks

• Subtask 1 [15 points]: K ≤ 10
• Subtask 2 [85 points]: No additional constraints

Sample Input 1

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

Sample Output 1

1
0
2
1
2

Explanation of Sample Output 1

• Child 1 chooses railways 1 and 4, for a total income of 3 + 6 = 9.
• Child 2 chooses railways 3 and 5, for a total income of 4 + 2 = 6.
• Railway 2 is not inherited and is donated.

Sample Input 2

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

Sample Output 2

4
3
2
1
2
1