1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-02-06 21:32
  5  * Filename     : uva_11183.cpp
  6  * Description     : 
  7  * ************************************************/
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <cmath>
 14 #include <algorithm>
 15 #include <queue>
 16 #include <stack>
 17 #include <vector>
 18 #include <set>
 19 #include <map>
 20 #define MP(a, b) make_pair(a, b)
 21 #define PB(a) push_back(a)
 22 
 23 using namespace std;
 24 typedef long long ll;
 25 typedef pair<int, int> pii;
 26 typedef pair<unsigned int,unsigned int> puu;
 27 typedef pair<int, double> pid;
 28 typedef pair<ll, int> pli;
 29 typedef pair<int, ll> pil;
 30 
 31 const int INF = 0x3f3f3f3f;
 32 const double eps = 1E-6;
 33 const int LEN = 1010;
 34 int Map[LEN][LEN];
 35 int pre[LEN], id[LEN], vis[LEN], in[LEN];
 36 
 37 struct E{
 38      int fr, to, val;
 39 };
 40 
 41 int zhuliu(int root, int n, int m, E edge[]){
 42     int ret = 0, u, v;
 43     while(1){
 44         for(int i=0; i<n; i++) in[i] = INF;
 45         for(int i=0; i<m; i++)
 46             if(edge[i].fr != edge[i].to && edge[i].val < in[edge[i].to]){
 47                 pre[edge[i].to] = edge[i].fr;
 48                 in[edge[i].to] = edge[i].val;
 49             }
 50         for(int i=0; i<n; i++)
 51             if(i != root && in[i] == INF) return INF;
 52         int tn = 0;
 53         memset(id, -1, sizeof id);
 54         memset(vis, -1, sizeof vis);
 55         in[root] = 0;
 56         for(int i=0; i<n; i++){
 57             ret += in[i];
 58             v = i;
 59             while(vis[v] != i && id[v] == -1 && v != root){
 60                 vis[v] = i;
 61                 v = pre[v];
 62             }
 63             if(v != root && id[v] == -1){
 64                 for(int u=pre[v]; u!=v; u=pre[u]) id[u] = tn;
 65                 id[v] = tn ++;
 66             }
 67         }
 68         if(tn == 0) break;
 69         for(int i=0; i<n; i++)if(id[i]==-1)id[i] = tn++;
 70         for(int i=0; i<m; ){
 71             v = edge[i].to;
 72             edge[i].fr = id[edge[i].fr];
 73             edge[i].to = id[edge[i].to];
 74             if(edge[i].fr != edge[i].to) edge[i++].val -= in[v];
 75             else swap(edge[i], edge[--m]);
 76         }
 77         n = tn;
 78         root = id[root];
 79     }
 80     return ret;
 81 }
 82 
 83 int main()
 84 {
 85 //    freopen("in.txt", "r", stdin);
 86 
 87     int a, b, val, T, n, m;
 88     E edge[40010];
 89     scanf("%d", &T);
 90     for(int kase = 1; kase <= T; kase++){
 91         memset(Map, INF, sizeof Map);
 92         scanf("%d%d", &n, &m);
 93         for(int i=0; i<m; i++){
 94              scanf("%d%d%d", &a, &b, &val);
 95              Map[a][b] = min(Map[a][b], val);
 96         }    
 97         int top = 0;
 98         for(int i=0; i<n; i++)
 99             for(int j=0; j<n; j++)
100                 if(Map[i][j] != INF){
101                      edge[top].fr = i;
102                      edge[top].to = j;
103                      edge[top++].val = Map[i][j];
104                 }
105         int ans = zhuliu(0, n, m, edge);
106         printf("Case #%d: ", kase);
107         if(ans == INF) printf("Possums!\n");
108         else printf("%d\n", ans);
109     }
110     return 0;
111 }