#include<fstream>
#include<cstring>
#define NMAX 1010
#define INF 100100

using namespace std;

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

int n, m, rez, C[NMAX][NMAX], F[NMAX][NMAX], vz[NMAX], q[NMAX*NMAX];

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

    f>>n>>m;

    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>c;
        C[x][y]=c;
        F[x][y]=0;
    }
}

void BFS(int nod)
{
    int i, p=1, u=1;

    memset(vz, 0, sizeof(vz));

    q[u]=nod; vz[1]=-1;

    while (!vz[n] && p<=u)
    {
        nod=q[p++];

        for (i=2; i<=n; ++i)
            if (!vz[i])
            {
                if (C[nod][i]>F[nod][i])
                {
                    vz[i]=nod;
                    q[++u]=i;
                }
                else
                    if (F[i][nod]>0)
                    {
                        vz[i]=-nod;
                        q[++u]=i;
                    }
            }
    }
}

void Construieste(int nod)
{
    int prec;

    if (nod!=1)
    {
        prec=vz[nod];

        if (prec>0)
        {
            rez=min(rez, C[prec][nod]-F[prec][nod]);

            Construieste(prec);

            F[prec][nod]+=rez;
        }
        else
        {
            prec*=-1;

            rez=min(rez, F[nod][prec]);

            Construieste(prec);

            F[nod][prec]-=rez;
        }
    }
}

void Solve()
{
    int sol=0;

    BFS(1);

    while (vz[n])
    {

        if (vz[n])
        {
            rez=INF;

            Construieste(n);
        }

        BFS(1);
    }

    for (int i=1; i<n; ++i) sol+=F[i][n];

    g<<sol<<"\n";

}

int main()
{
    Citeste();

    Solve();

    f.close();
    g.close();
    return 0;
}