AT_past202109_m バランス

[problemUrl]: https://atcoder.jp/contests/past202109-open/tasks/past202109_m $ N $ 頂点 $ M $ 辺の単純連結無向グラフ $ G $ が与えられます。 頂点には $ 1,\ldots,N $ の番号が、辺には $ 1,\ldots,M $ の番号がついており、辺 $ i $ は頂点 $ A_i $ と $ B_i $ を結んでいます。 辺 $ i $ には整数 $ C_i $ が書かれています。あなたは次の条件を満たすように、各頂点に $ 0 $ 以上の整数を書こうとしています。 条件：全ての辺 $ i $ について、頂点 $ A_i $ に書かれた数と頂点 $ B_i $ に書かれた数の和が $ C_i $ に等しい そのようなことが可能であれば一例を、不可能であればそのことを報告してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $

条件を満たすような数の書き込み方が存在しなければ `-1` と出力せよ。 存在するならば、頂点 $ i $ に書き込む数を $ i $ 行目に出力し、全部で $ N $ 行出力せよ。

### 注意 この問題に対する言及は、2021/10/02 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ N-1\ \leq\ M\ \leq\ 10^5 $ - $ 1\ \leq\ A_i\