Cho một đơn đồ thị vô hướng liên thông gồm $N$ đỉnh và $M$ cạnh. Các đỉnh của đồ thị được đánh số bằng các số tự nhiên phân biệt từ 1 đến $N$, và các cạnh được đánh số bằng các số tự nhiên phân biệt từ 1 đến $M$.

Cạnh thứ $j$ ($1 \le j \le M$) nối đỉnh $a_j$ và đỉnh $b_j$, có trọng số nguyên là $c_j$.

Bạn cần gán cho mỗi đỉnh một trọng số nguyên. Gọi trọng số được gán cho đỉnh thứ $i$ ($1 \le i \le N$) là $x_i$.

Tổng chi phí để gán trọng số cho các đỉnh bằng tổng giá trị tuyệt đối của trọng số mỗi đỉnh, tức là $|x_1| + |x_2| + \cdots + |x_N| = \sum_{i=1}^N |x_i|$.

Để đồ thị cân bằng, tổng trọng số của hai đỉnh được nối bởi mỗi cạnh phải bằng trọng số của cạnh đó. Nghĩa là, với mọi $j$ ($1 \le j \le M$), $x_{a_j} + x_{b_j}$ phải bằng $c_j$.

Ví dụ, xét một đồ thị gồm 5 đỉnh và 4 cạnh như hình bên dưới. Trong hình, số ghi trong vòng tròn biểu diễn số hiệu của đỉnh, và số ghi trên cạnh biểu diễn trọng số của cạnh đó.

Như hình bên dưới, ta có thể gán trọng số $[2, -7, 3, -5, 0]$ cho các đỉnh sao cho tổng trọng số của hai đỉnh được nối bởi mỗi cạnh bằng trọng số của cạnh đó. Trong hình dưới, số ghi trong vòng tròn biểu diễn trọng số của đỉnh.

Tổng chi phí là $|2| + |-7| + |3| + |-5| + |0| = 2 + 7 + 3 + 5 + 0 = 17$. Do không có cách nào làm cho tổng chi phí nhỏ hơn 17, nên cách trên là cách tối thiểu hóa tổng chi phí.

Nếu gán trọng số $[6, -3, -1, -9, 4]$ cho các đỉnh như dưới đây thì đồ thị cũng cân bằng, tuy nhiên trong trường hợp này tổng chi phí là 23 (lớn hơn 17), do đó cách dưới đây không phải là cách tối thiểu hóa tổng chi phí.

Hãy viết chương trình kiểm tra xem có thể gán trọng số cho các đỉnh để đồ thị cân bằng hay không, và nếu có thể, hãy tìm một cách sao cho tổng chi phí là nhỏ nhất.

Ghi chú

$|x|$ là ký hiệu giá trị tuyệt đối, bằng $-x$ nếu $x < 0$ và bằng $x$ nếu $x \ge 0$.

Giới hạn

• Tất cả các số được cho đều là số nguyên.
• $2 \le N \le 100\ 000$
• $1 \le M \le 200\ 000$
• Với mọi $j$ ($1 \le j \le M$):
  • $1 \le a_j \le N$, $1 \le b_j \le N$
  • $a_j \ne b_j$. Tức là không có cạnh nào nối một đỉnh với chính nó.
  • $-1\ 000\ 000 \le c_j \le 1\ 000\ 000$
• Với mọi $j, k$ ($1 \le j < k \le M$), $\{a_j, b_j\} \ne \{a_k, b_k\}$. Tức là có nhiều nhất một cạnh nối giữa mỗi cặp đỉnh phân biệt $(a, b)$.
• Đồ thị là đồ thị liên thông. Tức là khi chọn hai đỉnh bất kỳ trong đồ thị, luôn tồn tại đường đi trực tiếp hoặc gián tiếp nối hai đỉnh đó qua các cạnh.

Nhiệm vụ con

1. (6 điểm) $N = 3$, $M = 3$, và ba cạnh lần lượt nối các đỉnh 1 và 2, 2 và 3, 3 và 1.
2. (10 điểm) $N \le 1,000$, $M = N - 1$, và cạnh thứ $j$ ($1 \le j \le M$) nối đỉnh $j$ với đỉnh $j + 1$.
3. (11 điểm) $M = N - 1$, và cạnh thứ $j$ ($1 \le j \le M$) nối đỉnh $j$ với đỉnh $j + 1$.
4. (12 điểm) $M = N - 1$.
5. (13 điểm) $M = N$, và mỗi đỉnh được nối với đúng hai cạnh phân biệt.
6. (29 điểm) $N \le 1\ 000$.
7. (19 điểm) Không có giới hạn bổ sung nào.

Dữ liệu vào

Dòng đầu tiên chứa $N$ và $M$ theo thứ tự, cách nhau bởi một dấu cách.

$M$ dòng tiếp theo chứa thông tin về các cạnh. Trong đó, dòng thứ $j$ ($1 \le j \le M$) chứa ba số nguyên $a_j, b_j, c_j$ cách nhau bởi một dấu cách.

Dữ liệu ra

Nếu tồn tại cách gán trọng số nguyên cho các đỉnh sao cho đồ thị cân bằng:

• Dòng đầu tiên in ra Yes. Không phân biệt chữ hoa chữ thường.
• Dòng thứ hai in ra $N$ số nguyên $x_1, x_2, \ldots, x_N$ cách nhau bởi một dấu cách, biểu diễn trọng số được gán cho các đỉnh. Nếu có nhiều cách gán để đồ thị cân bằng đồng thời tối thiểu hóa tổng chi phí, bạn có thể in ra bất kỳ cách nào trong số đó.

Nếu không tồn tại cách gán trọng số nguyên cho các đỉnh sao cho đồ thị cân bằng:

• Dòng đầu tiên in ra No. Không phân biệt chữ hoa chữ thường.

Ví dụ

Dữ liệu vào 1

3 3
1 2 5
2 3 4
3 1 3

Dữ liệu ra 1

Yes
2 3 1

Dữ liệu vào 2

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

Dữ liệu ra 2

Yes
2 -7 3 -5 0