1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int maxn = 100 + 5, maxe = 100 * 100 / 2 + 5, INF = 0x3f3f3f3f;
 7 int n, m, lowc[maxn], pre[maxn], cost[maxn][maxn], Max[maxn][maxn];
 8 bool vis[maxn], used[maxn][maxn];
 9 
10 int Prim(int source) {
11     int ans = 0;
12     memset(vis, false, sizeof vis);
13     memset(Max, 0, sizeof Max);
14     memset(used, false, sizeof used);
15     for(int i = 2; i <= n; i ++) {
16         lowc[i] = cost[source][i];
17         pre[i] = source;
18     }
19     pre[source] = -1;
20     lowc[source] = 0;
21     vis[source] = true;
22     for(int i = 2; i <= n; i ++) {
23         int MIN = INF, k = -1;
24         for(int j = 1; j <= n; j ++)
25             if(!vis[j] && MIN > lowc[j]) {
26                 MIN = lowc[j];
27                 k = j;
28             }
29         if(MIN == INF) return -1;
30         vis[k] = true;
31         ans += MIN;
32         used[pre[k]][k] = used[k][pre[k]] = true;//这里记得要把现在访问的边进行标记
33         for(int j = 1; j <= n; j ++) {
34             if(vis[j] && j != k)
35                 Max[k][j] = Max[j][k] = max(Max[pre[k]][j], lowc[k]);//每次加入一个顶点，就将这个顶点到达其他顶点路径上的最大边权进行更新
36                 //为什么要这样更新呢？我们知道一个顶点在还没有加入最小生成树时它距离MST中各边顶点的最小值可以由它的父亲结点到j结点和它本身到MST结点的最小值的最大值来表示
37             if(!vis[j] && lowc[j] > cost[k][j]) {
38                 lowc[j] = cost[k][j];
39                 pre[j] = k;
40             }
41         }
42     }
43     return ans;
44 }
45 
46 int Second_Prim(int MST) {
47     int ans = INF;
48     for(int i = 1; i <= n; i ++)
49         for(int j = 1 + i; j <= n; j ++)
50             if(!used[i][j] && cost[i][j] != INF)
51                 ans = min(ans, MST - Max[i][j] + cost[i][j]);
52     return ans;
53 }
54 
55 int main () {
56     int t, u, v, w;
57     scanf("%d", &t);
58     while(t --) {
59         scanf("%d %d", &n, &m);
60         memset(cost, INF, sizeof cost);
61         for(int i = 1; i <= m; i ++) {
62             scanf("%d %d %d", &u, &v, &w);
63             cost[u][v] = cost[v][u] = w;
64         }
65         int MST = Prim(1);
66         int Second_MST = Second_Prim(MST);
67         if(Second_MST > MST)
68             printf("%d\n", MST);
69         else printf("Not Unique!\n");
70     }
71     return 0;
72 }