AT_tenka1_2015_final_g 天下一ゲーム

青木君准备了顶点数$N$、边数$M$的图表。图表的顶点以$1$～$N$的整数编号，边以$1$～$M$编号。这个图表不包括多个边和自循环。 青木君在所有的地方都写上了不同的$10^9$以下的正整数。 高桥将$10^9$以下的正整数写入所有顶点。此时，高桥君可以多次写同一个整数。 在高桥君和青木君写完整数的图表中，满足以下条件的边被称为“幸运之边”。 如果将边连接的顶点设为$u$，$v$，则该边上写的整数与顶点$u$和顶点$v$上写的整数中的小的那个一致。 高桥君得到的分数是“幸运之边”的总数。 因为青木君在边上画完整数的状态的图表被给予了，所以要求高桥君的得分最大化的整数的写法。 另外，在考虑多个答案时，回答其中一个。

入力は以下の形式で標準入力から与えられる。 > $ 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 グラフは連結とは限らない。