Edge Weights Reconstruction

Given an undirected graph with n nodes and m edges. Each edge \( (u_i,v_i) \) has an unknown weight \( a_i \). For any path defined as \( (p_0, p_1, \dots, p_k) \) where each consecutive pair \( (p_{i-1}, p_i) \) is connected by an edge (note that vertices and edges may repeat), the cost of the path is defined as

\( \sum_{i=1}^{k} a_{e_i} \),

where \( e_i \) denotes the index of the edge used between \( p_{i-1} \) and \( p_i \). Let \( f(x,y) \) be the minimum cost among all paths from node \( x \) to node \( y \) (with the convention that \( f(x,x)=0 \)).

You are given the values of n, m and for each edge \( (u_i,v_i) \) the corresponding value \( f(u_i,v_i) \). Determine whether there exists an assignment of weights \( a_i \) for the edges such that for every given edge \( (u_i,v_i) \) the shortest path between \( u_i \) and \( v_i \) in the graph (with weights \( a_i \)) is exactly \( f(u_i,v_i) \). If such an assignment exists, you are required to output one valid set of weights. Otherwise, output NO.

inputFormat

The first line of input contains two integers n and m denoting the number of nodes and edges, respectively.

Each of the next m lines contains three integers u_i, v_i, and \( f(u_i,v_i) \) representing an edge between nodes u_i and v_i along with the given shortest path cost for that edge.

outputFormat

If there exists a valid assignment of weights, print YES on the first line. On the next line, print m integers \( a_1, a_2, \dots, a_m \) corresponding to the weight assigned to each edge in the order they are given in the input.

If no valid assignment exists, simply print NO.

sample

3 3
1 2 2
2 3 3
1 3 5

YES
2 3 5