#include <fstream>
#include <queue>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
queue <int> q;
vector <int> v[1010],tatid;
int f[1010][1010], c[1010][1010], S, D,ok,nod,n,m,i,x,y,cost,drum,minn,flux,T[1010];
int bfs()
{
    q.push(S);
    ok=0;
    while(!q.empty())
    {
        nod=q.front();
        q.pop();
        for(auto it : v[nod])
        {
            if(it==D && c[nod][it]-f[nod][it]>0)
                ok=1;
            else
            {
                if(T[it]==0 && c[nod][it]-f[nod][it]>0)
                {
                    q.push(it);
                    T[it]=nod;
                }
            }
        }
    }
    return ok;
}
int main()
{
    fin>>n>>m;
    S=1; D=n;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        c[x][y]=cost;
        v[x].push_back(y);
        if(y==D)
            tatid.push_back(x);
    }
    drum=bfs();
    while(drum)
    {
        for(auto it : tatid)
        {
            if(T[it]!=0)
            {
                minn=999999999;
                T[D]=it;
                for(nod=D; nod != S ; nod=T[nod])
                    if(minn>c[T[nod]][nod] - f[T[nod]][nod])
                        minn=c[T[nod]][nod] - f[T[nod]][nod];
                if(minn>0)
                {
                    flux+=minn;
                    for(nod=D; nod != S ; nod=T[nod])
                        f[T[nod]][nod]+=minn;
                }
            }
        }
        for(i=1;i<=n;i++)
            T[i]=0;
        drum=bfs();
    }
    fout<<flux;

    return 0;
}