#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
const int nmax=1005;
vector<int> v[nmax];
int c[nmax][nmax],q[nmax],fl[nmax][nmax],prec[nmax];
int n,m,p,u,mn,start,node,i,x,y,z,flow,j;
bool ok;
bool bfs()
{
    p=1;u=1;q[u]=1;
    for(i=1;i<=n;i++)
        prec[i]=0;
    while(p<=u)
    {
        start=q[p];
        if(start==n) return true;
        p++;
        for(i=0;i<v[start].size();i++)
        {
           node=v[start][i];
           if(prec[node]==0)
           {
            if(fl[start][node]<c[start][node])
           {
               u++;
               q[u]=node;
               prec[node]=start;
           }
           else
           {
               if(fl[node][start]>0)
               {
                   u++;
                   q[u]=node;
                   prec[node]=-start;
               }
           }
           }
        }
    }
    return false;
}
int main()
{
    ifstream f("maxflow.in");
    ofstream g("maxflow.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        c[x][y]=z;
        v[x].push_back(y);
    }
    ok=1;
    while(ok)
    {
        ok=bfs();
        if(!ok) break;
        node=n;mn=(1<<30);
        while(node!=1)
        {
            if(node<0) node*=-1;
            if(prec[node]>0)
            {
                if(c[prec[node]][node]-fl[prec[node]][node]<mn)
                    mn=c[prec[node]][node]-fl[prec[node]][node];
            }
            else
            {
                if(fl[node][-prec[node]]<mn)
                   mn=fl[node][-prec[node]];
            }
            node=prec[node];
        }
        node=n;
        flow+=mn;
        while(node!=1)
        {
            if(prec[node]>0)
            {
                fl[prec[node]][node]+=mn;
                node=prec[node];
            }
            else
            {
                fl[node][-prec[node]]-=mn;
                node=-prec[node];
            }
        }
    }
    g<<flow;
    return 0;
}