#include<fstream>
#include<queue>
#include<cstring>
#include<cmath>
#define NMAX 1010

using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");

int n, m, s, d, cap[NMAX][NMAX], flux[NMAX][NMAX], marca[NMAX], di[NMAX], de[NMAX];
queue<int> q;

void Citeste()
{
    int i, x, y, c;

    f>>n>>m;

    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>c;
        cap[x][y]=c;
        ++di[y]; ++de[x];
    }
}

void Cauta()
{
    int i;

    for (i=1; i<=n; ++i)
    {
        if (!di[i]) s=i;
        if (!de[i]) d=i;
    }
}

void BFS()
{
    int i, z;

    q.push(s); marca[s]=NMAX;

    while(!q.empty())
    {
        z=q.front(); q.pop();
        for (i=1; i<=n; ++i)
            if (!marca[i])
                if (cap[z][i]>0 && flux[z][i]<cap[z][i])
                {
                    q.push(i);
                    marca[i]=z;
                }
                else
                    if (cap[i][z]>0 && flux[i][z]>0)
                    {
                        q.push(i);
                        marca[i]=-z;
                    }
    }
}

void Modifica()
{
    int mn=NMAX*NMAX, prec, cr;

    cr=d;
    while (marca[cr]!=NMAX)
    {
        prec=marca[cr];
        if(prec>0) mn=min(mn, cap[prec][cr]-flux[prec][cr]);
        else mn=min(mn, flux[cr][prec]);
        cr=abs((double)prec);
    }

    cr=d;
    while (marca[cr]!=NMAX)
    {
        prec=marca[cr];
        if(prec>0) flux[prec][cr]+=mn;
        else flux[cr][prec]-=mn;
        cr=abs((double)prec);
    }
}

void Solve()
{
    int s=0, i;
    do
    {
        memset(marca, 0, NMAX*sizeof(int));
        BFS();
        if (marca[d]) Modifica();
    }while (marca[d]);
    for (i=1; i<n; ++i) s+=flux[i][n];
    g<<s<<"\n";
}

int main()
{
    Citeste();
    Cauta();
    Solve();
    f.close();
    g.close();
    return 0;
}