グラフのバランス調整

$N$ 個の頂点と $M$ 本の辺からなる無向単純連結グラフがある。グラフの頂点には $1$ 以上 $N$ 以下の相異なる自然数番号が付けられており、辺には $1$ 以上 $M$ 以下の相異なる自然数番号が付けられている。

$j$ ($1 \le j \le M$) 番目の辺は頂点 $a_j$ と頂点 $b_j$ を結んでおり、整数の重み $c_j$ が付いている。

あなたはすべての頂点に整数の重みを割り当てなければならない。頂点 $i$ ($1 \le i \le N$) に割り当てる重みを $x_i$ とする。

頂点に重みを割り当てる総コストは、各頂点の重みの絶対値の和、すなわち $|x_1|+|x_2|+\dots+|x_N| = \sum_{i=1}^N |x_i|$ に等しい。

グラフのバランスが取れているとは、各辺が結ぶ $2$ つの頂点の重みの和がその辺の重みと等しいことを意味する。すなわち、すべての $j$ ($1 \le j \le M$) について、$x_{a_j} + x_{b_j}$ が $c_j$ と等しくなければならない。

例えば、以下のように $5$ 個の頂点と $4$ 本の辺からなるグラフを考える。図において頂点を表す円の中の数は頂点番号であり、辺を表す線に書かれた数は辺の重みである。

以下の図のように各頂点に [2, -7, 3, -5, 0] という重みを割り当てることで、各辺が結ぶ $2$ つの頂点の重みの和がその辺の重みと等しくなるようにできる。下の図において頂点を表す円の中の数は頂点の重みである。

総コストは $|2| + |-7| + |3| + |-5| + |0| = 2 + 7 + 3 + 5 + 0 = 17$ である。総コストを $17$ 未満にする方法はないため、上記の方法は総コストを最小化する方法である。

以下のように各頂点に [6, -3, -1, -9, 4] という重みを割り当ててもバランスの取れたグラフになるが、この場合の総コストは $17$ より大きい $23$ になるため、以下の方法は総コストを最小化する方法ではない。

グラフのバランスが取れるように各頂点に重みを割り当てることが可能かどうかを判定し、可能であればその中で総コストを最小化する方法を $1$ つ求めるプログラムを作成せよ。

注記

$|x|$ は $x < 0$ ならば $-x$、$x \ge 0$ ならば $x$ である絶対値記号である。

制約

• 与えられるすべての数は整数である。
• $2 \le N \le 100\,000$
• $1 \le M \le 200\,000$
• すべての $j$ ($1 \le j \le M$) について：
  • $1 \le a_j \le N, 1 \le b_j \le N$
  • $a_j \neq b_j$。すなわち、同一の頂点を結ぶ辺は存在しない。
  • $-1\,000\,000 \le c_j \le 1\,000\,000$
• すべての $j, k$ ($1 \le j < k \le M$) について、$\{a_j, b_j\} \neq \{a_k, b_k\}$。すなわち、相異なる $2$ 頂点の組 $(a, b)$ を結ぶ辺は高々 $1$ 本しか存在しない。
• グラフは連結グラフである。すなわち、グラフ内のどの $2$ 頂点を選んでも、辺を通じてその $2$ 頂点を直接または間接的に結ぶパスが存在する。

小課題

1. (6点) $N = 3, M = 3$ であり、$3$ 本の辺はそれぞれ頂点 $1$ と $2$、頂点 $2$ と $3$、頂点 $3$ と $1$ を結んでいる。
2. (10点) $N \le 1,000$ かつ $M = N - 1$ であり、$j$ 番目の辺 ($1 \le j \le M$) は頂点 $j$ と頂点 $j + 1$ を結んでいる。
3. (11点) $M = N - 1$ であり、$j$ 番目の辺 ($1 \le j \le M$) は頂点 $j$ と頂点 $j + 1$ を結んでいる。
4. (12点) $M = N - 1$ である。
5. (13点) $M = N$ であり、すべての頂点はちょうど $2$ 本の相異なる辺に接続している。
6. (29点) $N \le 1\,000$ である。
7. (19点) 追加の制約はない。

入力

1 行目に $N$ と $M$ が空白を区切りとして順に与えられる。

続く $M$ 行に各辺に関する情報が与えられる。このうち $j$ ($1 \le j \le M$) 行目には 3 つの整数 $a_j, b_j, c_j$ が空白で区切られて与えられる。

出力

グラフのバランスが取れるように各頂点に整数の重みを割り当てる方法が存在する場合：

• 1 行目に Yes を出力する。出力は大文字と小文字を区別しない。
• 2 行目に各頂点に割り当てた重みを表す $N$ 個の整数 $x_1, x_2, \dots, x_N$ を空白で区切って出力する。グラフのバランスが取れるようにしながら総コストを最小化する方法が複数存在する場合、それらのうちどれを出力してもよい。

グラフのバランスが取れるように各頂点に整数の重みを割り当てる方法が存在しない場合：

• 1 行目に No を出力する。出力は大文字と小文字を区別しない。

入出力例

入力 1

3 3
1 2 5
2 3 4
3 1 3

出力 1

Yes
2 3 1

入力 2

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

出力 2

Yes
2 -7 3 -5 0