P14415 [JOISC 2015] 遗产继承 / Inheritance

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。

### 样例 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 完成