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

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*,_{1}*i*, ...,_{2}*i*(_{m}*i*,_{1}*i*, ...,_{2}*i*are distinct) of_{m}*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
*i*^{th}line of the following**M**lines, there are three space-separated integers**A**,_{i}**B**,_{i}**C**. This means that railway_{i}*i*connects cities**A**and_{i}**B**and produces a profit of_{i}**C**yen in one year._{i}

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.

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**(1 ≤_{i}*i*≤**M**).- 1 ≤
**C**≤ 1 000 000 000 (1 ≤_{i}*i*≤**M**). **C**≠_{i}**C**(1 ≤_{j}*i*<*j*≤**M**).

Subtask 1 (15 points): **K** ≤ 10.

Subtask 2 (85 points): No additional constraints.

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

```
1
0
2
1
2
```

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.

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

```
4
3
2
1
2
1
```

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

Subtask | Score |
---|---|

1 | 15 |

2 | 85 |

3 | 0 |