1 #include<iostream>  2 #include<cstdio>  3 #include<cmath>  4 #include<cstring>  5 #include<queue>  6 using namespace std;  7 typedef long long LL;  8   9 const int maxn=2000+5; 10 const int INF=0x3f3f3f3f; 11  12 int map[maxn][maxn]; 13  14 struct Edge 15 { 16     int from, to, cap, flow, cost; 17     Edge(int u, int v, int c, int f, int w) :from(u), to(v), cap(c), flow(f), cost(w) {} 18 }; 19  20 struct MCMF 21 { 22     int n, m; 23     vector<Edge> edges; 24     vector<int> G[maxn]; 25     int inq[maxn]; 26     int d[maxn]; 27     int p[maxn]; 28     int a[maxn]; 29  30     void init(int n) 31     { 32         this->n = n; 33         for (int i = 0; i<n; i++) G[i].clear(); 34         edges.clear(); 35     } 36  37     void AddEdge(int from, int to, int cap, int cost) 38     { 39         edges.push_back(Edge(from, to, cap, 0, cost)); 40         edges.push_back(Edge(to, from, 0, 0, -cost)); 41         m = edges.size(); 42         G[from].push_back(m - 2); 43         G[to].push_back(m - 1); 44     } 45  46     bool BellmanFord(int s, int t, int &flow, LL & cost) 47     { 48         for (int i = 0; i<n; i++) d[i] = INF; 49         memset(inq, 0, sizeof(inq)); 50         d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; 51  52         queue<int> Q; 53         Q.push(s); 54         while (!Q.empty()){ 55             int u = Q.front(); Q.pop(); 56             inq[u] = 0; 57             for (int i = 0; i<G[u].size(); i++){ 58                 Edge& e = edges[G[u][i]]; 59                 if (e.cap>e.flow && d[e.to]>d[u] + e.cost){ 60                     d[e.to] = d[u] + e.cost; 61                     p[e.to] = G[u][i]; 62                     a[e.to] = min(a[u], e.cap - e.flow); 63                     if (!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; } 64                 } 65             } 66         } 67         if (d[t] == INF) return false; 68         flow += a[t]; 69         cost += (LL)d[t] * (LL)a[t]; 70         for (int u = t; u != s; u = edges[p[u]].from){ 71             edges[p[u]].flow += a[t]; 72             edges[p[u] ^ 1].flow -= a[t]; 73  74         } 75         return true; 76     } 77  78     int MincostMaxdflow(int s, int t, LL & cost) 79     { 80         int flow = 0; cost = 0; 81         while (BellmanFord(s, t, flow, cost) ); 82         return flow; 83     } 84 }t; 85  86 int n,m; 87  88 int main() 89 { 90     //freopen("D:\\input.txt", "r", stdin); 91     int T; 92     int kase=0; 93     scanf("%d",&T); 94     int u,v,d; 95     while(T--) 96     { 97         memset(map,0,sizeof(map)); 98         scanf("%d%d",&n,&m); 99         int src=http://www.mamicode.com/0,dst=2*n+1;100         t.init(dst+1);101         for(int i=1;i<=n;i++)102         {103             t.AddEdge(src,i,1,0);104             t.AddEdge(i+n,dst,1,0);105         }106         for(int i=0;i<m;i++)107         {108             scanf("%d%d%d",&u,&v,&d);109             if(map[u][v]==0 || map[u][v]>d)110             {111                 t.AddEdge(u,v+n,1,d);112                 t.AddEdge(v,u+n,1,d);113                 map[u][v]=map[v][u]=d;114             }115         }116         long long cost;117         int flow=t.MincostMaxdflow(src,dst,cost);118         printf("Case %d: ",++kase);119         if(flow==n)  printf("%d\n",cost);120         else printf("NO\n");121     }122     return 0;123 }