inheritance

Mr. JOI, the millionare who owns all of the IOI kingdom's railways, has passed away. According to his will, the railways are to be divided among his children.

There are N cities in the IOI kingdom, numbered from 1 to N. There are M railways connecting the cities, numbered from 1 to M. Railway i connects cities A_i and city B_i in both directions, and produces a profit of C_i yen in one year. C_i, ..., C_M are all pairwise distinct because some railways are used more by passengers and railways also have different operating costs. There might be more than one railway connecting two cities.

Mr. JOI's will gave the following instructions on the distribution of his railway:

• The railways are to be distributed to the K children of Mr. JOI. The children are numbered from 1 to K in decreasing order of age.
• Each child can pick any subset of the M railways (even an empty subset).
• Child 1 picks the subset of the M railways that he or she desires first. The remaining railways are left for Child 2. Child 2 then picks a subset of the railways, and so on. The K children pick their railways in this order.
• A child cannot pick a railway already previously chosen by one of his siblings. In other words, if child j has chosen railway i, all children k (k > j) are not allowed to choose railway i.
• A child cannot pick a set of railways that contains a cycle. In other words, if in a subset i₁, i₂, ..., i_m (i₁, i₂, ..., i_m are distinct) of m railways there exists a way to leave from one city and return to it, using only the railways in the subset each at most once, then no child is allowed to choose that subset of railways.
• The rest of the remaining railways are to be donated to the IOI kingdom.

Every child is greedy just like their father and will pick railways such that the total annual profit of his or her inheritance is as large as possible. The total annual profit of a set of railways is the sum of the annual profit for each railway in the set. For each child, the choice of railways that maximizes his or her total annual profit is unique. For each railway, determine who it is distributed to.

Given information about the IOI kingdom's railways and the number of children Mr. JOI had, write a program to find the eventual ownership of each railway.

Input

Read from standard input.

• On line 1, there are three space-separated integers N, M, K. These represent the number N of cities and the number M of railways in the IOI kingdom, and the number of children K of Mr. JOI.
• On the i^th line of the following M lines, there are three space-separated integers A_i, B_i, C_i. This means that railway i connects cities A_i and B_i and produces a profit of C_i yen in one year.

Output

Print to standard output.

• There will be M lines of output. On the i^th line, print the number of the child to whom railway i was given. Print 0 if it was donated to the IOI kingdom.

Constraints

All input data satisfies following constraints:

• 2 ≤ N ≤ 1 000.
• 1 ≤ M ≤ 300 000.
• 1 ≤ K ≤ 10 000.
• 1 ≤ A_i ≤ N, 1 ≤ B_i ≤ N (1 ≤ i ≤ M).
• A_i ≠ B_i (1 ≤ i ≤ M).
• 1 ≤ C_i ≤ 1 000 000 000 (1 ≤ i ≤ M).
• C_i ≠ C_j (1 ≤ i < j ≤ M).

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

Child 1 chooses railways 1, 4 from railways 1, 2, 3, 4, 5, obtaining a total annual profit of 3 + 6 = 9 yen. This is the maximum.

Child 2 chooses railways 3, 5 from railways 2, 3, 5, obtaining a total annual profit of 4 + 2 = 6 yen. This is the maximum.

The remaining railway 2 is donated to the IOI kingdom.

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

Explanation

The number of railways inherited by each child can differ. There can also exist a child that does not inherit any railways.