POJ 1679

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <string>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
// #include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ull, ull> puu;

#define inf (0x3f3f3f3f)
#define lnf (0x3f3f3f3f3f3f3f3f)
#define eps (1e-9)
#define fi first
#define se second

bool sgn(double a, string select, double b) {
    if(select == "==")return fabs(a - b) < eps;
    if(select == "!=")return fabs(a - b) > eps;
    if(select == "<")return a - b < -eps;
    if(select == "<=")return a - b < eps;
    if(select == ">")return a - b > eps;
    if(select == ">=")return a - b > -eps;
}


//--------------------------

const ll mod = 1000000007;
const int maxn = 110;


int n,m;

int par[maxn];

struct Edge {
    int u,v,w;
} edge[maxn*maxn];

vector<int> mstedge;

bool cmp(Edge a,Edge b) {
    return a.w<b.w;
}

int findx(int x) {
    if(par[x]==x)return x;
    else return par[x]=findx(par[x]);
}


int Kruskal(int n,int x) {
    for(int i=1; i<=n; i++) {
        par[i]=i;
    }
    int cnt=0;
    int ans=0;
    for(int i=0; i<m; i++) {
        if(i==x)continue;
        int u = edge[i].u;
        int v = edge[i].v;
        int w = edge[i].w;
        int t1 = findx(u);
        int t2 = findx(v);
        if(t1!=t2) {
            ans+=w;
            par[t1]=t2;
            cnt++;
            if(x==-1)mstedge.push_back(i);
        }
        if(cnt==n-1)break;
    }
    if(cnt<n-1)return -1;
    else return ans;
}

void solve() {
    int t;
    scanf("%d",&t);
    while(t--) {
        memset(edge,0,sizeof(edge));
        mstedge.clear();
        scanf("%d%d",&n,&m);
        for(int i=0; i<m; i++) {
            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
        }
        sort(edge,edge+m,cmp);
        int res = Kruskal(n,-1);
//        printf("res=%d\n",res);
        bool same = false;
        for(int i=0; i<mstedge.size(); i++) {
            int rr = Kruskal(n,mstedge[i]);
//            printf("rr=%d\n",rr);
            if(rr==res) {
                puts("Not Unique!");
                same=true;
                break;
            }
        }
        if(!same) {
            printf("%d\n",res);
        }
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
#endif
    // iostream::sync_with_stdio(false);
    solve();
    return 0;
}