Cactus Folding Plus

This is the hard version of "Cactus Folding." The two versions differ in the constraint on $l$, and the hard version requires you to print the coordinate $x_i$ of each vertex.

A cactus graph is an undirected graph in which every edge belongs to at most one simple cycle. Hzlo has a cactus graph, and each edge has a length. An edge of length $l$ that connects vertices $u$ and $v$ is written as the ordered triple $(u, v, l)$. While looking at his graph, Hzlo had this thought:

• Could some cactus graphs be folded into one dimension?

Before answering that, call a graph foldable into one dimension if it has the following property.

• Each vertex $i$ can be assigned a one-dimensional coordinate $x_i$ so that $|x_u - x_v| = l$ holds for every edge $(u, v, l)$.

Given a cactus graph, decide whether it is foldable into one dimension.

The first line contains two integers $n$ and $m$, the number of vertices and the number of edges, separated by a space. ($1 \le n \le 10^5$, $0 \le m \le \min(\lfloor 1.5(n-1) \rfloor, 10^5)$)

Each of the next $m$ lines describes one edge. The $i$-th of these lines contains the two vertices $u_i$ and $v_i$ that the $i$-th edge connects, and its length $l_i$, separated by spaces. ($1 \le u_i, v_i \le n$, $u \ne v$, $0 \le l_i \le 500$)

The graph has no multiple edges and no self-loops, and it is guaranteed to be a cactus graph.

If the graph is foldable into one dimension, print YES on the first line.

On the next line, print $n$ integers $x_1, x_2, \cdots, x_n$ separated by spaces. The $i$-th integer is the coordinate of vertex $i$, and it must lie in the range $[-10^9, 10^9]$. Any output that satisfies $|x_u - x_v| = l$ for every edge $(u, v, l)$ is accepted. Under the constraints of this problem, if the graph is foldable, an assignment of integers within $[-10^9, 10^9]$ that satisfies all edges always exists.

If the graph is not foldable, print NO on a single line.

The cactus graphs defined in this problem may not be connected.