Graph Path Mex Assignment

You are given an undirected graph with n vertices and m edges. The i-th edge connects vertices u_i and v_i and has an unknown weight a_i (a non‐negative integer).

For any path p = (p₀, p₁, ..., p_k) (where each adjacent pair (p_i-1, p_i) is an edge in the graph — vertices and edges may be repeated), define its cost by first collecting the multiset of weights of the edges in the path. Let the cost be the mex of this multiset, i.e. the smallest non-negative integer that does not appear among them. In mathematical notation, if the edges used (by their indices) are e₁, e₂, ..., e_k, then the cost is

[ \mathrm{mex}{a_{e_1},a_{e_2},\dots,a_{e_k}}. ]

For any two vertices x and y, define f(x, y) as the maximum cost among all paths connecting x and y.

You are given the numbers n and m, followed by m lines. For the i-th edge (u_i, v_i) the value f(u_i, v_i) is provided. Your task is to determine whether there exists an assignment of weights a_i to the edges such that for every edge (u_i, v_i) the maximum cost achievable over all paths from u_i to v_i equals the given value. If a solution exists, you must output one valid assignment.

Note: Since any path may use cycles and repeated edges, if the edges of a connected component receive weights whose union is exactly \(\{0,1,\dots, K-1\}\) (when \(K=f(x,y)>0\)) or do not include \(0\) (when \(K=0\)), then for any two vertices in that component f(x,y) equals \(K\). In a tree (a connected component with only one edge per connection), the only possible values are 0 or 1.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10⁵), representing the number of vertices and edges respectively. Each of the following m lines contains three integers u, v, and f, where u and v (1 ≤ u, v ≤ n) are the endpoints of an edge and f (0 ≤ f ≤ 10⁹) is the given value of f(u,v) for that edge.

outputFormat

If a valid assignment exists, output “YES” (without quotes) on the first line. On the second line, output m non-negative integers where the i-th integer represents the assigned weight a_i for the i-th edge (in the same order as the input). If there is no valid assignment, output “NO” (without quotes).

sample

3 2
1 2 1
2 3 1

YES
0 0