AT_abc373_d [ABC373D] Hidden Weights

[problemUrl]: https://atcoder.jp/contests/abc373/tasks/abc373_d $ N $ 頂点 $ M $ 辺の有向グラフが与えられます。$ j $ 番目の有向辺は頂点 $ u_j $ から頂点 $ v_j $ に向かっており、重み $ w_j $ を持っています。 各頂点に $ -10^{18} $ 以上 $ 10^{18} $ 以下の整数を書き込む方法であって、次の条件を満たすものを $ 1 $ つ見つけてください。 - 頂点 $ i $ に書き込まれている値を $ x_i $ とする。すべての辺 $ j=1,2,\dots,M $ について、$ x_{v_j}\ -\ x_{u_j}\ =\ w_j $ が成り立つ。 与えられる入力について、条件を満たす書き込み方が少なくとも $ 1 $ つ存在することが保証されます。

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

頂点 $ i $ に書き込む整数を $ x_i $ として、$ x_1,x_2,\dots,x_N $ をこの順に空白区切りで $ 1 $ 行で出力せよ。答えが複数ある場合、どれを出力しても良い。

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ M\ \leq\ \min\{2\ \times\ 10^5,N(N-1)/2\} $ - $ 1\ \leq\ u_j,\ v_j\ \leq\ N $ - $ u_j\ \neq\ v_j $ - $ i\ \neq\ j $ なら $ (u_i,v_i)\ \neq\ (u_j,v_j) $ かつ $ (u_i,v_i)\ \neq\ (v_j,u_j) $ - $ |w_j|\ \leq\ 10^9 $ - 入力はすべて整数 - 条件を満たす書き込み方が少なくとも $ 1 $ つ存在する ### Sample Explanation 1 $ x=(3,5,2) $ とすることで、$ x_2-x_1=w_1=2,x_2-x_3=w_2=3,x_3-x_1=w_3=-1 $ となり、条件を満たします。 他にも、たとえば $ x=(-1,1,-2) $ としても正解となります。 ### Sample Explanation 2 他にも、たとえば $ x=(0,-5,4,1) $ や $ x=(5,0,4,1) $ としても正解となります。