1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5  6 using namespace std; 7 const int MAXN=105; 8 const int inf=10000000; 9 int map[MAXN][MAXN]; int f[MAXN][MAXN];10 bool exist[MAXN][MAXN],used[MAXN][MAXN];11 int least[MAXN],pre[MAXN]; bool vis[MAXN]; 12 int n,m,ans1,ans2;13 14 void prim(){15     memset(f,0,sizeof(f));16     least[1]=0;17     for(int i=2;i<=n;i++){18         least[i]=map[1][i];19         if(least[i]!=inf)20         pre[i]=1;21     }22     vis[1]=true;23     for(int i=1;i<=n;i++){24         int min=inf,p=-1;25         for(int k=1;k<=n;k++){26             if(least[k]<min&&!vis[k]){27                 p=k; min=least[k];28             }29         }30 31         if(p==-1) return ;32         ans1+=min;33         used[pre[p]][p]=used[p][pre[p]]=1;34         for(int j=1;j<=n;j++){35         if(vis[j])36         f[j][p]=max(f[j][pre[p]],map[pre[p]][p]);37         f[p][j]=f[j][p];38         }39         vis[p]=true;40         for(int k=1;k<=n;k++){41             if(!vis[k]&&map[p][k]<least[k]){42                 least[k]=map[p][k];43                 pre[k]=p;44             }45         }46     }47 }48 49 void secondT(){50     ans2=inf;51     for(int i=1;i<=n;i++){52         for(int j=1;j<=n;j++){53             if(exist[i][j]&&!used[i][j]&&ans1 + map[i][j] - f[i][j] < ans2)54             ans2=ans1 + map[i][j] - f[i][j];55         }56     }57 }58 59 int main(){60     int T; 61     scanf("%d",&T);62     while(T--){63         scanf("%d%d",&n,&m);64         int u,v,d;65         ans1=ans2=0;66         memset(exist,-1,sizeof(exist));67         for(int i=1;i<=n;i++){68             for(int j=i;j<=n;j++)69             map[i][j]=map[j][i]=inf;70         }71         for(int i=1;i<=m;i++){72             scanf("%d%d%d",&u,&v,&d);73             map[u][v]=map[v][u]=d;74             exist[u][v]=exist[v][u]=1;75         }76         memset(pre,-1,sizeof(pre));77         memset(used,0,sizeof(used));78         memset(vis,false,sizeof(vis));79         prim();80         secondT();81         if(ans1==ans2)82         printf("Not Unique!\n");83         else printf("%d\n",ans1);84     }85     return 0;86 }