G - 天下一ゲーム Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君と青木君は暇つぶしのためにグラフを使ったゲームをすることにした。

ゲームは次の 3 ステップで行われる。

  • 青木君が頂点数 N、辺数 M のグラフを用意する。グラフの頂点は 1 ～ N の整数で番号付けされており、辺は1 ～ M で番号付けされている。このグラフは多重辺や自己ループを含まない。
  • 青木君がすべての辺に相異なる 10^9 以下の正の整数を書き込む。
  • 高橋君がすべての頂点にそれぞれ 10^9 以下の正の整数を書き込む。このとき、高橋君は同じ整数を何度も書くことができる。

高橋君と青木君が整数を書き終わったグラフにおいて、以下の条件を満たす辺を「ラッキーな辺」と呼ぶことにする。

  • その辺が結ぶ頂点を u, v とすると、その辺に書かれている整数が頂点 u と頂点 v に書かれている整数のうち小さい方と一致する。

高橋君の得る点数は「ラッキーな辺」 の総数である。

青木君が辺に整数を書き終わった状態のグラフが与えられるので、高橋君の得点が最大になるような頂点への整数の書き込み方を求めよ。

なお、答えが複数考えられるときは、そのいずれか 1 つを答えよ。

入力

入力は以下の形式で標準入力から与えられる。

N M
u_1 v_1 a_1
u_2 v_2 a_2
:
u_M v_M a_M
  • 1 行目には青木君が用意したグラフの頂点数を表す整数 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 行目には高橋君の得点が最大になるように整数を書き込んだ時に 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

グラフは連結とは限らない。