#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int flux[1010][1010];
int c[1010][1010];
int tata[1010];
int viz[1010],flow;
int coad[1015];
int Q,x,y,z,N,act,M,fmin;
vector<int> g[1010];
int BF()
{printf("!");
    coad[0]=1;
   int st=0,dr=1;
    for(int i=1;i<=N;++i)
    {
    viz[i]=0;
    tata[i]=0;
    }

    viz[1]=1;
    while(st<dr)
    {
   // printf("!");
        act=coad[st];
        for(int i=0;i<g[act].size();++i)
        {

            Q = g[act][i];
            if(c[act][Q] == flux[act][Q] || viz[Q])
                continue;
            viz[Q]=1;
            coad[dr++]=Q;
            tata[Q]=act;
                if(Q==N)
                    return 1;

        }
        ++st;
    }
    return 0;
}

int main()
{
freopen("maxflow.in","r",stdin);
freopen("maxflow.out","w",stdout);
scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i)
    {
    scanf("%d%d%d",&x,&y,&z);
    c[x][y]+=z;
    g[x].push_back(y);
    g[y].push_back(x);

    }

    for(flow=0; BF(); flow+=fmin)
    {
    fmin=10101000;
        for(int nod= N;nod!=1;nod=tata[nod])
        {
            fmin=min(fmin,c[tata[nod]][nod] - flux[tata[nod]][nod]);
        }
        for(int nod=N;nod!=1;nod=tata[nod])
        {
            flux[tata[nod]][nod]+=fmin;
            flux[nod][tata[nod]]-=fmin;
        }
    }
    printf("%d ",flow);
}