M - Balance Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

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

問題文

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 に等しい

そのようなことが可能であれば一例を、不可能であればそのことを報告してください。

制約

  • 2 \leq N \leq 10^5
  • N-1 \leq M \leq 10^5
  • 1 \leq A_i < B_i \leq N
  • (A_i,B_i) は相異なる
  • 0 \leq C_i \leq 10^9
  • 与えられるグラフは連結
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

出力

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

入力例 1

3 2
1 2 2
2 3 1

出力例 1

1
1
0

頂点 1 に 1、頂点 2 に 1、頂点 3 に 0 を書くと、条件を満たすことが確かめられます。

他にも、頂点 1 に 2、頂点 2 に 0、頂点 3 に 1 を書いた場合も条件を満たします。

入力例 2

3 3
1 2 0
2 3 0
1 3 2

出力例 2

-1

頂点に書き込む数は 0 以上の整数でなければならないことに注意してください。

Score : 6 points

Warning

Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices are numbered 1, \ldots, N, and the edges are numbered 1, \ldots, M. Edge i connects Vertices A_i and B_i.

Edge i has an integer C_i written on it. You are about to write an integer not less than 0 on each vertex so that the following condition is satisfied.

Condition: For every edge i, the sum of the numbers written on Vertices A_i and B_i equals C_i.

If this is possible, show one way to do it; if it is impossible, report that fact.

Constraints

  • 2 \leq N \leq 10^5
  • N-1 \leq M \leq 10^5
  • 1 \leq A_i < B_i \leq N
  • The pairs (A_i, B_i) are distinct.
  • 0 \leq C_i \leq 10^9
  • The given graph is connected.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

Output

If there is no way to write numbers to satisfy the condition, print -1.
Otherwise, print the number to write on Vertex i in the i-th line, for a total of N lines.

Sample Input 1

3 2
1 2 2
2 3 1

Sample Output 1

1
1
0

It can be verified that writing 1 on Vertex 1, 1 on Vertex 2, and 0 on Vertex 3 satisfies the condition.

Another way to satisfy the condition is to write 2 on Vertex 1, 0 on Vertex 2, and 1 on Vertex 3.

Sample Input 2

3 3
1 2 0
2 3 0
1 3 2

Sample Output 2

-1

Note that the numbers to write on the vertices must be integers not less than 0.