← 返回题目列表

AtCoder · tenka1_2015_final_g

G. 天下一游戏

中文机器翻译题面 查看原题

問題文

高桥和青木决定玩一个用图表来消磨时间的游戏。

下一场比赛 它是通过 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

图不一定是连通的。