给你一个带权有向图。设每个顶点 $i$ 的势能为 $\Phi_i$。设 $w_{uv}$ 为边 $(u, v)$ 的权重。定义新权重为 $w'_{uv} = w_{uv} + \Phi_u - \Phi_v$。

请找到一组整数势能 $\Phi_i$，使得所有边的新权重 $w'$ 都相等。

输入格式

输入的第一行包含一个整数 $t$，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示图中的顶点数和边数（$1 \le n \le 300\,000$，$0 \le m \le 300\,000$）。

接下来的 $m$ 行，每行包含三个整数 $x_i$、$y_i$ 和 $w_i$，分别表示一条边的起点、终点和权重（$1 \le x_i, y_i \le n$，$-10^9 \le w_i \le 10^9$）。

保证图中无自环且无重边。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $600\,000$。

输出格式

对于每个测试用例，第一行输出 “YES”（如果存在整数解）或 “NO”（如果不存在）。

如果存在解，在下一行输出 $n$ 个整数，表示各顶点的势能。势能的绝对值不能超过 $10^{18}$。保证如果存在解，则一定存在满足上述限制的解。

如果存在多个解，输出其中任意一个即可。

样例

输入样例 1

2
5 4
1 2 -1
2 3 2
3 4 1
4 5 179
5 5
1 2 1
2 3 1
3 4 1
4 5 0
5 1 2

输出样例 1

YES
0 -1 1 2 181
YES
0 0 0 0 -1