Se tiene un grafo conexo simple no dirigido compuesto por $N$ vértices y $M$ aristas. Los vértices del grafo están numerados con números naturales distintos del $1$ al $N$, y las aristas están numeradas con números naturales distintos del $1$ al $M$.

La arista $j$ ($1 \le j \le M$) conecta el vértice $a_j$ y el vértice $b_j$, y tiene un peso entero $c_j$.

Debes asignar un peso entero a cada vértice. Sea $x_i$ el peso asignado al vértice $i$ ($1 \le i \le N$).

El costo total de asignar pesos a los vértices es igual a la suma de los valores absolutos de los pesos de cada vértice, es decir, $|x_1|+|x_2|+\dots+|x_N| = \sum_{i=1}^N |x_i|$.

Para que el grafo esté equilibrado, la suma de los pesos de los dos vértices conectados por cada arista debe ser igual al peso de dicha arista. Es decir, para todo $j$ ($1 \le j \le M$), $x_{a_j} + x_{b_j}$ debe ser igual a $c_j$.

Por ejemplo, considera un grafo compuesto por $5$ vértices y $4$ aristas como se muestra a continuación. En la figura, el número dentro del círculo que representa un vértice es el número del vértice, y el número en la línea que representa una arista es el peso asignado a la arista.

Como se muestra en la siguiente figura, es posible asignar los pesos $[2, -7, 3, -5, 0]$ a los vértices para que la suma de los pesos de los dos vértices conectados por cada arista sea igual al peso de la arista. En la figura siguiente, el número dentro del círculo que representa un vértice es el peso del vértice.

El costo total es $|2| + |-7| + |3| + |-5| + |0| = 2 + 7 + 3 + 5 + 0 = 17$. Como no existe ninguna forma de hacer que el costo total sea menor que $17$, este método minimiza el costo total.

Si se asignan los pesos $[6, -3, -1, -9, 4]$ a los vértices como se muestra a continuación, el grafo también estará equilibrado; sin embargo, en este caso el costo total es $23$, que es mayor que $17$, por lo que este método no minimiza el costo total.

Escribe un programa que determine si es posible asignar pesos a los vértices de manera que el grafo quede equilibrado y, en caso de ser posible, encuentre un método que minimice el costo total.

Nota

$|x|$ denota el valor absoluto, que es $-x$ si $x < 0$ y $x$ si $x \ge 0$.

Restricciones

• Todos los números dados son enteros.
• $2 \le N \le 100\,000$
• $1 \le M \le 200\,000$
• Para todo $j$ ($1 \le j \le M$):
  • $1 \le a_j \le N$, $1 \le b_j \le N$
  • $a_j \ne b_j$. Es decir, no hay aristas que conecten un vértice consigo mismo.
  • $-1\,000\,000 \le c_j \le 1\,000\,000$
• Para todo $j, k$ ($1 \le j < k \le M$), $\{a_j, b_j\} \ne \{a_k, b_k\}$. Es decir, hay a lo sumo una arista entre cualquier par de vértices distintos $(a, b)$.
• El grafo es conexo. Es decir, para cualquier par de vértices del grafo, existe un camino que conecta directa o indirectamente ambos vértices a través de las aristas.

Subtareas

1. (6 puntos) $N = 3$, $M = 3$, y las tres aristas conectan los vértices 1 y 2, 2 y 3, y 3 y 1, respectivamente.
2. (10 puntos) $N \le 1,000$, $M = N - 1$, y la arista $j$ ($1 \le j \le M$) conecta el vértice $j$ y el vértice $j + 1$.
3. (11 puntos) $M = N - 1$, y la arista $j$ ($1 \le j \le M$) conecta el vértice $j$ y el vértice $j + 1$.
4. (12 puntos) $M = N - 1$.
5. (13 puntos) $M = N$, y cada vértice está conectado exactamente a dos aristas distintas.
6. (29 puntos) $N \le 1\,000$.
7. (19 puntos) Sin restricciones adicionales.

Entrada

En la primera línea se dan $N$ y $M$ en ese orden, separados por un espacio.

En las siguientes $M$ líneas se describe la información de cada arista. La $j$-ésima ($1 \le j \le M$) de estas líneas contiene tres enteros $a_j$, $b_j$ y $c_j$, separados por un espacio.

Salida

Si existe una forma de asignar pesos enteros a los vértices de modo que el grafo esté equilibrado:

• Imprime Yes en la primera línea. La salida no distingue entre mayúsculas y minúsculas.
• En la segunda línea, imprime $N$ enteros $x_1, x_2, \dots, x_N$ separados por un espacio, que representen los pesos asignados a cada vértice. Si existen múltiples formas que minimicen el costo total manteniendo el grafo equilibrado, puedes imprimir cualquiera de ellas.

Si no existe una forma de asignar pesos enteros a los vértices de modo que el grafo esté equilibrado:

• Imprime No en la primera línea. La salida no distingue entre mayúsculas y minúsculas.

Ejemplos

Entrada 1

3 3
1 2 5
2 3 4
3 1 3

Salida 1

Yes
2 3 1

Entrada 2

5 4
1 3 5
2 3 -4
4 2 -12
5 3 3

Salida 2

Yes
2 -7 3 -5 0