AT_tenka1_2015_final_g 天下一ゲーム

[problemUrl]: https://atcoder.jp/contests/tenka1-2015-final/tasks/tenka1_2015_final_g 高橋君と青木君は暇つぶしのためにグラフを使ったゲームをすることにした。 ゲームは次の $ 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) $の値は相異なる。

出力は $ N $ 行からなる。 $ i $ 行目には高橋君の得点が最大になるように整数を書き込んだ時に $ i $ 番目の頂点に書き込まれる正の整数を出力せよ。 各整数の値は $ 10^9 $ を超えてはならない。 出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ 1\ ≦\ N\ ≦\ 20 $を満たすデータセットに正解した場合は $ 90 $ 点が与えられる。 - $ 1\ ≦\ N\ ≦\ 40 $を満たすデータセットに正解した場合はさらに $ 130 $ 点が与えられる。合計で$ 220 $点となる。 ### Sample Explanation 1 上記出力例のように整数を書き込むと、$ 1,\ 2,\ 3,\ 5,\ 6,\ 7 $番目の辺が「ラッキーな辺」となる。よって高橋君は $ 6 $ 点を得る。 これより多い点数を得ることのできる書き込み方はない。 ### Sample Explanation 2 $ 4,\ 7,\ 9,\ 10 $番目の辺が「ラッキーな辺」になる。 ### Sample Explanation 3 グラフは連結とは限らない。