先做一遍prim，求出最小生成树的value，和路径。每次去掉一条路径上的边，再做最小生成树，若出现新的value和第一次的value相等，则次小生成树不唯一。否则，取枚举过程中最小的一个value即可。
#include<stdio.h>
#include<string.h>
#define N 110
#define M 1<<27
int g[N][N], pre[N],low[N];
bool visit[N];
struct Now
{
int x, y, z;
}now[N], cur;
int prim(int n){
int i,j,k, ans=0;
for(i=1; i<=n; i++){
low[i]=g[1][i];
pre[i]=1;
visit[i]=false;
}
visit[1]=true;
k=1;
for(i=2; i<=n; i++){
int mn=-1, p;
for(j=1; j<=n; j++)
if(!visit[j] && (mn==-1 || low[j]<mn)){
mn=low[j];
p=j;
}
if(mn==-1) break;
ans+=mn;
k=p;
visit[k]=true;
for(j=1; j<=n; j++){
if(!visit[j] && low[j]>g[k][j]){
low[j]=g[k][j];
pre[j]=k;
}
}
}
return ans;
}
int main()
{
int i,j,n,m,ca,x,y,z;
scanf("%d", &ca);
while(ca--){
scanf("%d %d", &n, &m);
for(i=0 ; i<=n ; i++)
for(j=0; j<=n; j++)
g[i][j]=M;
for(i=0; i<m; i++){
scanf("%d %d %d", &x, &y, &z);
g[x][y]=g[y][x]=z;
}
int value=prim(n);
j=0;
for(i=2; i<=n; i++){
now[j].x=i;
now[j++].y=pre[i];
}
int t=0;
for(i=0; i<n-1; i++){
int a, b, aa, bb;
a=now[i].x;
b=now[i].y;
now[i].z=g[a][b];
g[a][b]=g[b][a]=M;
if(i>0){
aa=now[i-1].x;
bb=now[i-1].y;
g[aa][bb]=g[bb][aa]=now[i-1].z;
}
int tmp=prim(n);
if(tmp==value){
t=1;
break;
}
}
if(t)
printf("Not Unique!\n");
else
printf("%d\n", value);
}
return 0;
}