Problem Description

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 \).

Each edge \( i \) has an integer \( C_i \) written on it. You are trying to write integers greater than or equal to \( 0 \) on each vertex to satisfy the following condition:

Condition: For every edge \( i \), the sum of the numbers written on vertices \( A_i \) and \( B_i \) equals \( C_i \).

If it is possible to do so, provide an example; if not, report that it is impossible.

Input Format

The input is given from the standard input in the following format:

\( N \) \( M \) \( A_1 \) \( B_1 \) \( C_1 \) \( \vdots \) \( A_M \) \( B_M \) \( C_M \)

Output Format

If no such way of writing numbers exists, output -1.
If it exists, output the number to be written on vertex \( i \) in the \( i \)-th line, for a total of \( N \) lines.

Sample Input and Output

Sample Input #1

3 2
1 2 2
2 3 1

Sample Output #1

1
1
0

Sample Input #2

3 3
1 2 0
2 3 0
1 3 2

Sample Output #2

-1

Notes/Hints

Note

Discussion of this problem is prohibited until 2021/10/02 18:00 JST. If mentioned, it may lead to claims for damages. It is okay to publish the total score or certification level after the exam, but please refrain from disseminating information about which problems were solved.

Constraints

• \( 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) \) are distinct
• \( 0 \leq C_i \leq 10^9 \)
• The given graph is connected
• All inputs are integers

Sample Explanation 1

Writing \( 1 \) on vertex \( 1 \), \( 1 \) on vertex \( 2 \), and \( 0 \) on vertex \( 3 \) satisfies the condition. Another way is writing \( 2 \) on vertex \( 1 \), \( 0 \) on vertex \( 2 \), and \( 1 \) on vertex \( 3 \).

Sample Explanation 2

Note that the numbers written on the vertices must be integers greater than or equal to \( 0 \).

见题面 Input 部分

见题面 Output 部分