AT_kupc2021_e PERMST

[problemUrl]: https://atcoder.jp/contests/kupc2021/tasks/kupc2021_e $ N $ 頂点 $ M $ 辺の無向単純連結グラフ $ G $ があります。 $ G $ の頂点には $ 1 $ から $ N $ までの番号がついていて、辺には $ 1 $ から $ M $ までの番号がついています。 $ G $ の辺 $ i $ は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 $ 0 $ および $ 1 $ からなる長さ $ M $ の数列 $ C\ =\ (c_1,\ c_2,\ \ldots,\ c_M) $ が与えられます。 $ c_i $ が $ 0 $ のとき辺 $ i $ は青色で塗られていて、$ c_i $ が $ 1 $ のとき辺 $ i $ は赤色で塗られています。 ここで、$ c_i\ =\ 1 $ となる $ i $ はちょうど $ N-1 $ 個あり、赤色の辺は $ G $ の全域木をなしています。 次の条件を満たす、$ 1 $ から $ M $ までの整数を並び替えた順列 $ P\ =\ (p_1,\ p_2,\ \ldots,\ p_M) $ のうち、辞書順最小のものを求めてください。 - $ G $ の辺 $ i $ の重みを $ p_i $ とすると、$ G $ の最小全域木に使われている辺はすべて赤色である。 - このとき、$ G $ の最小全域木は一意に定まることに注意せよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ c_1 $ $ u_2 $ $ v_2 $ $ c_2 $ $ \vdots $ $ u_M $ $ v_M $ $ c_M $

条件を満たす順列 $ P\ =\ (p_1,\ p_2,\ \ldots,\ p_M) $ のうち、辞書順最小のものを次の形式で出力し、末尾で改行せよ。 余計な空白や、末尾以外での改行を含めてはならない。(10/31 14:21 追記) > $ p_1 $ $ p_2 $ $ \ldots $ $ p_M $

### 制約 - $ 2\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ N\ -\ 1\ \le\ M\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ u_i\