問題文
高桥和青木决定玩一个用图表来消磨时间的游戏。
下一场比赛 它是通过 3 步骤完成的。
- 青木有顶点数 准备一个 N、辺数 M 的图表。图表的顶部是 1 ~ N 用整数编号,边为 编号为1 ~ M 。该图不包含多条边或自环。
- 青木君无处不在不同 10^9 在下面写一个正整数。
- 高桥君处于每一个巅峰 10^9 在下面写一个正整数。这时,高桥就可以一遍又一遍地写同一个整数。
在高桥和青木写完整数的图中,我们将满足以下条件的边称为“幸运边”。
- 由该边连接的顶点是 u, v ,那一边写的整数就是顶点 匹配 u 与 边 v 中写入的较小整数。
高桥得到的分数是“幸运边”的总数。
给定 Aoki 已完成在边上写入整数的图,找到一种将整数写入顶点的方法,以使 Takahashi 的得分最大化。
如果有多个可能的答案,请选择其中之一。 1 回答一。
入力
输入是按以下格式从标准输入给出的。
N M u_1 v_1 a_1 u_2 v_2 a_2 : u_M v_M a_M
- 1 表示 Aoki 准备的图的顶点数的整数位于第一行。 N (1 ≦ N ≦ 40) 和一个表示边数的整数 M (1 ≦ M ≦ N×(N-1)/2)用空格分隔。
- 2 从线 M 行 i 在线 i 第一条边连接 2 顶点数 u_i, v_i (1 ≦ u_i < v_i ≦ N)和写在侧面的整数 a_i(1 ≦ a_i ≦ 10^9) 用空格分隔。
- 给定的图不包含多条边或自环。
- a_i(1 ≦ i ≦ N)具有不同的值。 给出
部分点
针对此问题设置了部分分数。
- 1 ≦ N ≦ 20的数据集 给出 90 点。 如果您正确回答了所有满足
- 1 ≦ N ≦ 40的数据集,则进一步 给出 130 点。总共220点。
出力
输出是 由 N 行组成。 i 当你在第 1 行写一个整数来最大化高桥的分数时, 打印写入第 i 个顶点的正整数。 每个整数的值为 不得超过 10^9 。 在输出末尾插入换行符。
入力例1
8 7 1 2 1 2 3 3 3 4 2 4 5 7 5 6 4 6 7 6 7 8 5
出力例1
1 3 4 2 4 9 6 5
如果您按照上面的输出示例写入一个整数, 第1, 2, 3, 5, 6, 7边是“幸运边”。因此,高桥君 6 获得积分。
没有比这更能获得分数的写作方法了。 第
入力例2
5 10 1 2 1 1 3 3 1 4 5 1 5 7 2 3 2 2 4 4 2 5 6 3 4 8 3 5 11 4 5 9
出力例2
7 6 11 9 17
4, 7, 9, 10边成为“幸运边”。
入力例3
12 14 1 2 14 1 3 6 3 5 11 2 5 10 2 3 1 3 6 13 2 6 8 8 10 2 7 9 12 10 11 3 8 9 9 6 10 4 6 7 7 9 12 5
出力例3
14 15 6 1 10 8 14 9 12 4 3 5
图不一定是连通的。