#include<fstream>
#include<cstring>
#include<queue>
#define NMAX 1010
#define CMAX 110000

using namespace std;

int n, m, cap[NMAX][NMAX], flux[NMAX][NMAX], di[NMAX], de[NMAX], s, d, marca[NMAX];

queue<int> q;

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

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

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

void Cauta()
{
    int i;

    for (i=1; i<=n; ++i)
    {
        if (!de[i]) d=i;
        if (!di[i]) s=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 && cap[z][i]-flux[z][i]>0)
                {
                    marca[i]=z;
                    q.push(i);
                }
                else
                    if (cap[z][i]<0 && flux[z][i]>0)
                    {
                        marca[i]=-z;
                        q.push(i);
                    }
            }
    }
}

void Modifica()
{
    int drum[NMAX], i, nod=d, urm, lg=0, mn=CMAX, mni=CMAX, u, p, aux;

    while (marca[nod]!=NMAX)
    {
        drum[++lg]=nod; urm=marca[nod];
        if (urm>0)
        {
            mn=min(mn, cap[urm][nod]-flux[urm][nod]);
            nod=urm;
        }
        else
        {
            urm*=-1;
            mni=min(mni, flux[nod][urm]);
            nod=urm;
        }
    }
    drum[++lg]=nod;
    p=1; u=lg;
    while (p<u)
    {
        aux=drum[p];
        drum[p++]=drum[u];
        drum[u--]=aux;
    }
    for (i=2; i<=lg; ++i)
    {
        nod=drum[i];
        urm=marca[nod];
        if (urm>0) flux[urm][nod]+=mn;
        else flux[nod][-urm]-=mn;
    }
}

void Solve()
{
    do
    {
        memset(marca, 0, NMAX*sizeof(int));
        BFS();
        if (marca[d]) Modifica();
    }while (marca[d]);
}

void Scrie()
{
    int s=0, i;
    for (i=1; i<=n; ++i) s+=flux[i][n];
    g<<s<<"\n";
}

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