Description

You have an undirected graph, and each edge has a color: red or black.

What you need to do is assign a real-valued weight to each node such that:

• For every black edge, the sum of the weights of its two endpoints is $1$.
• For every red edge, the sum of the weights of its two endpoints is $2$.
• The sum of the absolute values of all node weights is minimized.

Find one such assignment of node weights.

Input Format

The first line contains two integers $N, M$, representing the number of nodes and the number of edges.
The nodes are numbered from $1$ to $N$.
The next $M$ lines each contain three integers $a, b, c$, describing an edge whose endpoints are $a$ and $b$. If $c$ is $1$, then this edge is black; if $c$ is $2$, then this edge is red.

Output Format

If there is a solution, first output YES on the first line, then output $N$ integers on the second line representing one possible set of node weights.
If there are multiple solutions, output any one of them.
If there is no solution, output a single line containing the string NO.

4 4
1 2 1
2 3 2
1 3 2
3 4 1

YES
0.5 0.5 1.5 -0.5

2 1
1 2 1

YES
0.3 0.7

3 2
1 2 2
2 3 2

YES
0 2 0

3 4
1 2 2
2 2 1
2 1 1
1 2 2

NO

Hint

Judging Method

Your output is considered correct if and only if:

• For every edge, the error between the sum of the weights of its two endpoints and the required value for that edge is at most $10^{-6}$.
• The error between the sum of the absolute values of all node weights and the standard answer is at most $10^{-6}$.

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (5 pts): $N \le 5$, $M \le 14$.
• Subtask 2 (12 pts): $N \le 100$.
• Subtask 3 (17 pts): $N \le 1000$.
• Subtask 4 (24 pts): $N \le 10^4$.
• Subtask 5 (42 pts): no special restrictions.

For $100\%$ of the testdata, $1 \le N \le 10^5$, $0 \le M \le 2 \times 10^5$.

This problem uses a Special Judge.

Translated by ChatGPT 5