#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int i,j,x,y,n,m,v,c[1001][1001],f[1001][1001],t[1005],d[1005],fmax=0;

vector <int> vd[1001],vi[1001];

int drum()
{
    queue <int> q;
    int x;
    for(i=0;i<=n;i++)
    {
        d[i]=0;
        t[i]=0;
    }
    //t[1]=-1;
    d[1]=1;
    /*while(!q.empty())
    {
        q.pop();
    }*/
    q.push(1);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        //cout << x << ' ';
        //cout << '\n';
        if(x==n)
            return 1;
        for(int i : vd[x])
        {
            if(c[x][i]!=0 && c[x][i]>f[x][i] && !d[i])
            {
                q.push(i);
                t[i]=x;
                d[i]=1;
            }
        }
        for(int i : vi[x])
        {
            if(f[i][x]!=0 && !d[i])
            {
                d[i]=1;
                t[i]=x;
                q.push(i);
            }
        }
        /*for(i=1;i<=n;i++)
        {
            if(c[x][i]!=0 && c[x][i]>f[x][i] && !d[i])
            {
                q.push(i);
                t[i]=x;
                d[i]=1;
            }
            if(f[i][x]!=0 && !d[i])
            {
                d[i]=1;
                t[i]=x;
                q.push(i);
            }
        }*/
    }
    return 0;
}

void flux()
{
    int x=n, vrmin=1000000;
    while(t[x]!=0)
    {
        if(c[x][t[x]]!=0)
        {
            //invers
            vrmin=min(vrmin,f[x][t[x]]);
        }
        else
        {
            //direct
            vrmin=min(vrmin,c[t[x]][x]-f[t[x]][x]);
        }
        x=t[x];
    }
    x=n;
    while(t[x]!=0)
    {
        if(c[x][t[x]]!=0)
        {
            //invers
            f[x][t[x]]-=vrmin;
        }
        else
        {
            //direct
            f[t[x]][x]+=vrmin;
        }
        x=t[x];
    }
}

int main()
{
    bool nou;
    fin >> n >> m;
    for(i=0;i<m;i++)
    {
        fin >> x >> y >> v;
        c[x][y]=v;
        vd[x].push_back(y);
        vi[y].push_back(x);
    }
    do
    {
        nou=drum();
        flux();
        /*for(i=1;i<=n;i++)
        {
            cout << t[i] << ' ';
        }
        cout << '\n';
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                cout << f[i][j] << ' ';
            }
            cout << '\n';
        }
        cout << "\n\n\n";*/
    } while(nou);
    for(i=2;i<=n;i++)
    {
        fmax+=f[1][i];
    }
    fout << fmax;

}