#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define inf 0x3f3f3f3fusing namespace std;int map[50][50],v[50],pre[1000];int n,m;int bfs(int s,int t){    memset(v,0,sizeof(v));    memset(pre,-1,sizeof(pre));    pre[s]=s;    queue
          
           q; q.push(s); v[s]=1; while(!q.empty()) { int tt=q.front(); q.pop(); for(int i=1; i<=n; i++) { if(map[tt][i]&&v[i]==0) { v[i]=1; pre[i]=tt; q.push(i); if(i==t) { return 1; } } } } return 0;}int EK(int s,int t){ int ans=0; while(bfs(s,t)==1) { int min1=inf; for(int i=t; i!=s; i=pre[i]) { if(min1>map[pre[i]][i]) { min1=map[pre[i]][i]; } } for(int i=t; i!=s; i=pre[i]) { map[pre[i]][i]-=min1; map[i][pre[i]]+=min1; } ans+=min1; } return ans;}int main(){ int T,x,y,z; scanf("%d",&T); for(int i=1; i<=T; i++) { scanf("%d%d",&n,&m); memset(map,0,sizeof(map)); while(m--) { scanf("%d%d%d",&x,&y,&z); map[x][y]+=z; } printf("Case %d: %d\n",i,EK(1,n)); EK(1,n); } return 0;}
          
         
        
       
      
     

 #include <iostream>

#include <string.h>

#include <stdlib.h>

#include <stdio.h>

#include <queue>

#include<algorithm>

#define inf 0x3f3f3f3f

using namespace std;

int n,m,tt;

struct node

{

    int x,y,c;

    int next;

}edge[10001];

int head[101],dis[101];

void init()

{

    memset(head,-1,sizeof(head));

    tt=0;

}

void add(int xx,int yy,int zz)

{

    edge[tt].x=xx;

    edge[tt].y=yy;

    edge[tt].c=zz;

    edge[tt].next=head[xx];

    head[xx]=tt++;

    edge[tt].x=yy;

    edge[tt].y=xx;

    edge[tt].c=0;

    edge[tt].next=head[xx];

    head[xx]=tt++;

}

int bfs(int s,int t)

{

     queue<int>q;

     memset(dis,-1,sizeof(dis));

     q.push(s);

     dis[s]=0;

     while(!q.empty())

     {

         int w=q.front();

         q.pop();

         for(int i=head[w];i!=-1;i=edge[i].next)

         {

             if(dis[edge[i].y]==-1&&edge[i].c>0)

             {

                 dis[edge[i].y]=dis[w]+1;

                 q.push(edge[i].y);

             }

         }

     }

    if(dis[t]>=0) return 1;

    return 0;

}

int dinic(int x,int maxt)

{

     int a;

     if(x==n) return maxt;

     for(int i=head[x];i!=-1;i=edge[head[x]].next)

     {

         if(dis[edge[i].y]==x+1&&edge[i].c>0&&(a==min(maxt,edge[i].c)))

         {

             ,mhgr

         }

     }

}

int main()

{

    int T,xx,yy,zz,ans;

    scanf("%d",&T);

    for(int i=1;i<=T;i++)

    {

        init();

        ans=0;

        scanf("%d%d",&n,&m);

        while(m--)

        {

            scanf("%d%d%d",&xx,&yy,&zz);

            add(xx,yy,zz);

        }

        while(bfs(1,n)==1)

        {

            ans+=dinic(1,inf);

        }

        printf("Case %d: %d\n",i,ans);

    }

    return 0;

}