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 Ai and city Bi in both directions, and produces a profit of Ci yen in one year. Ci, ..., CM 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 i1, i2, ..., im (i1, i2, ..., im 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.
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 ith line of the following M lines, there are three space-separated integers Ai, Bi, Ci. This means that railway i connects cities Ai and Bi and produces a profit of Ci yen in one year.
Print to standard output.
- There will be M lines of output. On the ith line, print the number of the child to whom railway i was given. Print 0 if it was donated to the IOI kingdom.
All input data satisfies following constraints:
- 2 ≤ N ≤ 1 000.
- 1 ≤ M ≤ 300 000.
- 1 ≤ K ≤ 10 000.
- 1 ≤ Ai ≤ N, 1 ≤ Bi ≤ N (1 ≤ i ≤ M).
- Ai ≠ Bi (1 ≤ i ≤ M).
- 1 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ M).
- Ci ≠ Cj (1 ≤ i < j ≤ M).
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
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
The number of railways inherited by each child can differ. There can also exist a child that does not inherit any railways.