题目描述

IOI 国所有铁路的拥有者、大富豪 JOI 先生已经去世。根据遗嘱，铁路将被分割并继承。

IOI 国有 $N$ 个城市，以及连接这些城市的 $M$ 条铁路。城市编号为 1 到 $N$，铁路编号为 1 到 $M$。第 $i$ 条铁路连接城市 $A_i$ 和城市 $B_i$，为双向线路，每年可产生 $C_i$ 日元的收益。由于乘客数量和票价各异，$C_1, \dots, C_M$ 各不相同。可能存在多条铁路连接同一对城市。

遗嘱中规定了铁路分割继承的方法如下：

• 铁路将由 JOI 先生的 $K$ 个子女继承。子女按年龄从高到低依次编号为 1 到 $K$。
• 每个子女继承若干条铁路（可能为 0 条）。
• 首先，从 $M$ 条铁路中，子女 1 选择若干条作为自己的继承部分；接着，从剩余铁路中，子女 2 决定自己的继承部分；依此类推，$K$ 个子女依次决定继承部分。
• 任何子女都不能继承已被更年长子女继承的铁路。即，若铁路 $i$ 已被子女 $j$ 继承，则任何更年轻的子女 $k$（$k > j$）均不能继承该铁路。
• 任何子女在选择继承部分时，必须确保所选铁路不构成环路。即，若存在一条由铁路 $i_1, i_2, \dots, i_m$（其中 $i_1, i_2, \dots, i_m$ 互不相同）组成的路径，使得从某个城市出发，经过这些铁路后能返回原城市，则任何子女均不能独自继承所有这些铁路。
• 未被任何子女继承的铁路将捐赠给 IOI 国。

每个子女都像其父亲一样贪婪，希望自己的继承部分的年收益总和尽可能大。已证明，对于每个子女，存在唯一一种选择方式，使其继承部分的年收益总和达到最大值。请确定每条铁路由谁继承。

题目

给定 IOI 国铁路的信息和 JOI 先生子女的人数，编写程序求出每条铁路由谁继承。

输入格式

从标准输入读取以下内容：

• 第一行包含三个整数 $N, M, K$，以空格分隔。这表示 IOI 国有 $N$ 个城市和 $M$ 条铁路，JOI 先生有 $K$ 个子女。
• 接下来的 $M$ 行中，第 $i$ 行（$1 \le i \le M$）包含三个整数 $A_i, B_i, C_i$，以空格分隔。这表示第 $i$ 条铁路连接城市 $A_i$ 和城市 $B_i$（双向），年收益为 $C_i$ 日元。

输出格式

输出共 $M$ 行。第 $i$ 行（$1 \le i \le M$）输出继承第 $i$ 条铁路的子女编号。若该铁路被捐赠给 IOI 国，则输出 0。

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

1
0
2
1
2

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

提示

样例 1 解释

• 子女 1 从铁路 1, 2, 3, 4, 5 中选择铁路 1 和 4 进行继承。此时继承铁路的年收益总和为 $3 + 6 = 9$ 日元，这是最大值。
• 子女 2 从剩余铁路 2, 3, 5 中选择铁路 3 和 5 进行继承。此时继承铁路的年收益总和为 $4 + 2 = 6$ 日元，这是最大值。
• 剩余铁路 2 将捐赠给 IOI 国。

样例 2 解释

继承铁路的数量可能因子女而异。可能存在完全没有继承任何铁路的子女。

数据范围

所有输入数据满足以下条件：

• $2 \le N \le 1000$
• $1 \le M \le 300000$
• $1 \le K \le 10000$
• $1 \le A_i \le N$, $1 \le B_i \le N$（$1 \le i \le M$）
• $A_i \ne B_i$（$1 \le i \le M$）
• $1 \le C_i \le 1000000000$（$1 \le i \le M$）
• $C_i \ne C_j$（$1 \le i < j \le M$）

子任务

子任务 1 [15 分]

• $K \le 10$

子任务 2 [85 分]

无额外限制。

翻译由 Qwen3-235B 完成