题目描述

Cuber QQ 正在整理一张神秘地图。地图上一共有 $n$ 个地点，编号为 $1,2,\dots,n$。对于任意两个地点 $i,j$，Cuber QQ 希望最终确定一个整数距离 $d(i,j)$。

一份合法的距离表需要满足：

• 对任意地点 $i$，有 $d(i,i)=0$；
• 对任意两个不同地点 $i,j$，有 $d(i,j)=d(j,i)$，并且 $d(i,j)>0$；
• 对任意三个地点 $i,j,k$，都满足：$d(i,j)\le d(i,k)+d(k,j)$，也就是说，从 $i$ 到 $j$ 的距离，不能比“先到 $k$，再从 $k$ 到 $j$”更长。

现在，Cuber QQ 已经知道了 $m$ 条距离记录。第 $t$ 条记录为 $u_t,\ v_t,\ w_t$，表示地点 $u_t$ 与地点 $v_t$ 之间的距离必须恰好等于 $w_t$。

现在 Cuber QQ 想请你判断，是否存在一种方法，补全所有尚未确定的距离，使得所有已知记录都被保留，并且整张距离表合法。

输入格式

第一行一个整数 $T$，表示测试数据组数。

对于每一组测试数据，第一行包含两个整数 $n,m$，表示地点数量和已知的距离记录。接下来的 $m$ 行，每行三个整数 $u_i,v_i,w_i$，表示一条记录。

输出格式

对于每组数据，输出一行。如果存在合法的补全方案，输出 YES；否则输出 NO。

样例

4
4 4
1 2 3
2 3 4
1 3 7
3 4 2
3 3
1 2 2
2 3 2
1 3 5
3 2
1 2 1
2 3 1
3 1
1 3 100

YES
NO
YES
YES

样例解释

对于第 1 组数据，已知 $d(1,2)=3,\quad d(2,3)=4,\quad d(1,3)=7$。由于从 $1$ 经过 $2$ 到 $3$ 的距离为 $3+4=7$。与已知的 $d(1,3)=7$ 不冲突，因此可以合法补全。

对于第 2 组数据，根据三角不等式，必须满足 $d(1,3)\le d(1,2)+d(2,3)=4$，但输入中要求 $d(1,3)=5$，发生矛盾，所以不存在合法补全方案。

对于第 3 组数据，只知道 $d(1,2)=1$ 与 $d(2,3)=1$，没有要求 $d(1,3)$ 必须是多少，所以可以令 $d(1,3)=2$。

对于第 4 组数据，虽然它和第 3 组数据的点数相同，但不同测试数据互相独立。只知道 $d(1,3)=100$，可以合法补全。

数据规模与约定

对于所有测试数据，保证：$2\le T\le 20,2\le n\le 400,0\le m\le \frac{n(n-1)}{2},1\le u_t < v_t \le n,1\le w_t \le 10^9$。同一组数据中，任意一对地点至多出现一条距离记录。对于一个输入文件内的所有测试数据，保证 $\sum n\le 500$。

原题链接

原题链接