P12069 [THOI 2013] 阿里巴巴与四十大盗【征集数据及 SPJ】

搬运自 [2013 年清华大学信息学邀请赛](https://gitlink.org.cn/thusaa/thoi2013)。 注：本题官方数据与配置文件丢失。

阿里巴巴所在村子被凶残的四十大盗洗劫一空，包括阿里巴巴在内的 $n$ 个村民也被强盗们囚禁在村子里。为了防止这 $n$ 个人逃跑，强盗们还用一些绳子把这些人绑了起来，每根绳子的两端各绑着一个人。出于求生的本能，阿里巴巴和村民们想在不被强盗发现的情况下逃离村子。他们决定分成 $k$ 组出逃，两个不同组的人之间不能有绳子相连。他们每解开一条绳子都需要花一定的时间（解开不同绳子可能需要花不同的时间，且所有人同一时刻只能解一条绳子）。解绳子花的时间越长就越有可能被强盗们发现，请你给出一种用时最少的解绳方案，使得他们可以分成 $k$ 组逃离村子。

输入文件的第一行包含三个整数 $n,m,k$，表示一共有 $n$ 个村民（从 $1$ 到 $n$ 编号），他们之间有 $m$ 对人被绑在了一起，要分成 $k$ 组人离开。 接下来的行描述村民之间被捆绑的关系，其中第 $i$ 行包含三个整数 $a_i,b_i,c_i(1\le a_i,b_i\le n)$，表示 $a_i$ 和 $b_i$ 两个人被绑在一根绳子的两端，解开它需要 $c_i$ 的时间。

输出文件一共 $n$ 行，每行一个整数 $d_i(1\le d_i\le k)$，其中第 $i$ 行的整数 $d_i$ 表示第 $i$ 个人被分到的组号。 **注意：分组方案与分组编号不唯一，只需输出一种解决方案。**

### 【对样例的说明】 样例输入中的捆绑方式如下图所示（图中边上所标数字为绳子的编号）：  分成三组人的最优解决方案有两种：解开绳子 $\{1,2,3\}$ 或者 $\{1,5,6\}$ ，其中样例输出为第一种方案。 ### 【评分标准】 每个测试点单独评分。 本题设有 $5$ 个评分参数 $t_1,t_2,t_3,t_4,t_5(t_1\le t_2\le t_3\le t_4\le t_5)$。设你给出的方案所需解绳子的时间为 $t$， - 若 $t\le t_1$，则该测试点你将得到满分； - 若 $t_1