1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 #define mt(a,b) memset(a,b,sizeof(a))  5 using namespace std;  6 const int inf=0x3f3f3f3f;  7 class SecondMinST_Prim{///次小生成树(无向图基于Prim)o(MV^2)  8     typedef int typec;///边权的类型  9     static const int MV=128;///点的个数 10     int n,pre[MV]; 11     bool vis[MV],used[MV][MV]; 12     typec minst,cimin,cost[MV][MV],Max[MV][MV],lowc[MV]; 13     void Prim() { 14         minst=0; 15         mt(vis,0); 16         mt(Max,0); 17         mt(used,0); 18         vis[0]=true; 19         pre[0]=-1; 20         for(int i=1; i<n; i++) { 21             lowc[i]=cost[0][i]; 22             pre[i]=0; 23         } 24         lowc[0]=0; 25         for(int i=1; i<n; i++) { 26             typec sma=inf; 27             int p=-1; 28             for(int j=0; j<n; j++) 29                 if(!vis[j]&&sma>lowc[j]) { 30                     sma=lowc[j]; 31                     p=j; 32                 } 33             if(sma==inf){ 34                 minst=-1; 35                 return ; 36             } 37             minst+=sma; 38             vis[p]=true; 39             used[p][pre[p]]=used[pre[p]][p]=true; 40             for(int j=0; j<n; j++) { 41                 if(vis[j]) 42                     Max[j][p]=Max[p][j]=max(Max[j][pre[p]],lowc[p]); 43                 if(!vis[j]&&lowc[j]>cost[p][j]) { 44                     lowc[j]=cost[p][j]; 45                     pre[j]=p; 46                 } 47             } 48         } 49     } 50     void smst() { 51         cimin=inf; 52         for(int i=0; i<n; i++) 53             for(int j=i+1; j<n; j++) 54                 if(cost[i][j]!=inf && !used[i][j]) { 55                     cimin=min(cimin,minst+cost[i][j]-Max[i][j]); 56                 } 57         if(cimin==inf) cimin=-1; 58     } 59 public: 60     void init(int tn){///传入点的个数，下标0开始 61         n=tn; 62         for(int i=0;i<n;i++){ 63             for(int j=0;j<n;j++){ 64                 cost[i][j]=i==j?0:inf; 65             } 66         } 67     } 68     void add(int u,int v,typec w){ 69         if(cost[u][v]>w){ 70             cost[u][v]=w; 71             cost[v][u]=w; 72         } 73     } 74     void solve(){ 75         Prim(); 76         smst(); 77     } 78     typec getmin(){ 79         return minst; 80     } 81     typec getci(){ 82         return cimin; 83     } 84 }gx; 85 int main(){ 86     int t,n,m; 87     while(~scanf("%d",&t)){ 88         while(t--){ 89             scanf("%d%d",&n,&m); 90             gx.init(n); 91             while(m--){ 92                 int u,v,w; 93                 scanf("%d%d%d",&u,&v,&w); 94                 gx.add(u-1,v-1,w); 95             } 96             gx.solve(); 97             if(gx.getci()==gx.getmin()){ 98                 puts("Not Unique!"); 99             }100             else{101                 printf("%d\n",gx.getmin());102             }103         }104     }105     return 0;106 }