30053 - 唯一最小生成树

通过次数

1

提交次数

1

时间限制 : 1 秒
内存限制 : 128 MB

给出一个有权值的无向图 G,请你判断 G 的最小生成树是否唯一。如果不唯一,输出 No,如果唯一,输出最小生成树的边权之和。

输入

第一行:一个数 T,表示测试组数(1 \le T \le 20)。

后面每一个测试用例:

第一行:2 个数 n, m,中间用空格分割,对应点的数量和边的数量(1 \le n \le 1001 \le m \le \frac{n(n-1)}{2})。

后面 m 行,每行 3 个数:u, v, w,表示点 u 和点 v 之间有边,权值为 w1 \le u, v \le n1 \le w_i \le 10000)。

输出

如果不唯一,输出 No;如果唯一,输出最小生成树的边权之和。

样例

输入

2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2

输出

3
No

提示

样例解释

  • 第一个测试用例:最小生成树唯一,边权和为 1 + 2 = 3
  • 第二个测试用例:图是一个环,所有边权均为 2,有多个最小生成树(任选三条边),不唯一,输出 No