#include<iostream>#include<cstring>#define rep(i,n) for(int i=0;i<n;i++)#define fab(i,a,b) for(int i=a;i<=b;i++)#define sf scanf#define pf printf#include<cstdio>const int N = 200;int n,m;int map[N][N],combine[N],vis[N],wet[N];int S,T,minCut;void init(){     memset(map,0,sizeof map);     sf("%d%d",&n,&m);     rep(i,m){        int u,v,w;        sf("%d%d%d",&u,&v,&w);        u--;v--;        map[u][v]+=w;map[v][u]+=w;     }}#define INF 0x3f3f3f3fvoid find(){    int Max,tmp;    memset(vis,0,sizeof vis);    memset(wet,0,sizeof wet);    S=T=-1;    rep(i,n){        Max=-INF;        rep(j,n){            if(!combine[j]&&!vis[j]&&wet[j]>Max){                tmp=j;                Max=wet[j];            }        }        if(T==tmp)return;        S=T;T=tmp;        minCut=Max;        vis[tmp]=1;        rep(j,n){            if(!combine[j]&&!vis[j]){                wet[j]+=map[tmp][j];            }        }    }}int Stoer_Wagner(){    memset(combine,0,sizeof combine);    int ans=INF;    rep(i,n-1){        find();        if(minCut<ans)ans=minCut;        if(ans==0)return ans;        combine[T]=1;        rep(j,n){            if(!combine[j]){                map[S][j]+=map[T][j];                map[j][S]+=map[j][T];            }        }    }    return ans;}void solve(){    pf("%d\n",Stoer_Wagner());}int main(){    int t;sf("%d",&t);    rep(cas,t){        pf("Case #%d: ",cas+1);        init();        solve();    }    return 0;}