Balancing a Graph

There is an undirected, simple, connected graph with N vertices and M edges. The vertices are labeled with distinct natural numbers from 1 to N, and the edges are labeled with distinct natural numbers from 1 to M.

Edge j (1 ≤ j ≤ M) connects vertex aj and vertex bj and has an integer weight cj.

You must assign an integer weight to every vertex. Let xi be the weight assigned to vertex i (1 ≤ i ≤ N).

The total cost of the assignment is the sum of the absolute values of the vertex weights, that is, |x1| + |x2| + ... + |xN|.

For the graph to be balanced, the sum of the weights of the two vertices connected by each edge must equal that edge's weight. In other words, for every j (1 ≤ j ≤ M), xaj + xbj = cj.

For example, consider the graph below with 5 vertices and 4 edges. In the figure, the number inside each circle representing a vertex is the vertex's label, and the number on each line representing an edge is the edge's weight.

As in the figure below, assigning the weights [2, -7, 3, -5, 0] to the vertices makes the sum of the weights of the two vertices connected by each edge equal to that edge's weight. In the figure below, the number inside each circle representing a vertex is the vertex's weight.

The total cost is |2| + |-7| + |3| + |-5| + |0| = 2 + 7 + 3 + 5 + 0 = 17. No assignment can make the total cost less than 17, so the above assignment minimizes the total cost.

Assigning the weights [6, -3, -1, -9, 4] to the vertices as below also yields a balanced graph, but in this case the total cost is 23, which is greater than 17, so the assignment below does not minimize the total cost.

Write a program that checks whether it is possible to assign weights to the vertices so that the graph is balanced, and if so, finds one assignment that minimizes the total cost.

The first line gives N and M in that order, separated by a space.

The next M lines give information about each edge. The j-th line (1 ≤ j ≤ M) gives three integers aj, bj, cj separated by single spaces.

If there exists an assignment of integer weights to the vertices that makes the graph balanced:

• Print Yes on the first line. The output is case-insensitive.
• On the second line, print the N integers x1, x2, ..., xN representing the weights assigned to the vertices, separated by single spaces. If there are multiple assignments that balance the graph and minimize the total cost, you may print any of them.

If there is no assignment of integer weights to the vertices that makes the graph balanced:

• Print No on the first line. The output is case-insensitive.

• All numbers in the input are integers.

• 2 ≤ N ≤ 100 000

• 1 ≤ M ≤ 200 000

• For every j (1 ≤ j ≤ M):

  • 1 ≤ aj ≤ N, 1 ≤ bj ≤ N
  • aj ≠ bj. That is, there is no edge connecting a vertex to itself.
  • -1 000 000 ≤ cj ≤ 1 000 000

• For every j, k (1 ≤ j < k ≤ M), {aj, bj} ≠ {ak, bk}. That is, there is at most one edge between any pair of distinct vertices (a, b).

• The graph is connected. That is, for any two vertices in the graph, there is a path connecting them, directly or indirectly, through edges.

|x| is the absolute value sign: it equals -x when x < 0 and x when x ≥ 0.