#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define pb push_back
#define TR(C, i)\
    for(i = C.begin(); i != C.end(); i++)

using namespace std;

int N, M;
const int nmax = 1024;
int C[nmax][nmax], F[nmax][nmax], L[nmax][nmax];
int fl[nmax], Cap[nmax], E[nmax], sint;

void read()
{
    ifstream in ("maxflow.in");
    in >> N >> M;
    int i, a, b, c;
    for(i = 1; i <= M; i++)
    {
        in >> a >> b >> c;
        C[a][b] += c;
        L[b][a] += c;
    }
}

void calc()
{
    int i, in, out, j;
    sint = N - 2;
    for(i = 2; i < N; i++)
    {
        in = out = 0;
        E[i] = 1;
        for(j = 1; j <= N; j++)
            in += L[i][j],
            out += C[i][j];
        Cap[i] = min(in, out);
    }
}

int flow;

void Push(int v)
{
    queue <int> Q;
    Q.push( v );
    memset(fl, 0, sizeof(fl));

    fl[v] = Cap[v];
    int i, j, u, f0;
    while(!Q.empty())
    {
        u = Q.front();
        Q.pop();
        f0 = fl[u];
        //while(f0)
            for(i = 1; i <= N && f0; i++)
                if(C[u][i])
                {
                    if(fl[i] == 0 && i != N)
                        Q.push(i);

                    if(C[u][i] <= f0)
                    {
                        F[u][i] = C[u][i];
                        C[u][i] = 0;
                        L[i][u] = 0;
                        fl[i] += F[u][i];
                        f0 -= F[u][i];
                    }
                    else
                    {
                        F[u][i] = f0;
                        fl[i] += f0;
                        C[u][i] -= f0;
                        f0 = 0;
                    }
                    if(u != v)
                        Cap[u] = Cap[u] - F[u][i];
                    if(u != v && Cap[u] == 0)
                    {
                        sint--;
                        E[u] = 0;
                        for(j = 1; j <= N; j++)
                            C[u][j] = L[u][j] = 0;
                    }
                }
            if(f0)
                flow -= f0;
    }
}

void Pull(int v)
{
    queue <int> Q;
    Q.push( v );
    memset(fl, 0, sizeof(fl));

    fl[v] = Cap[v];
    int i, j, u, f0;
    while(!Q.empty())
    {
        u = Q.front();
        Q.pop();
        f0 = fl[u];
       // while(f0)
            for(i = 1; i <= N; i++)
                if(L[u][i])
                {
                    if(fl[i] == 0 && i != 1)
                        Q.push(i);

                    if(L[u][i] <= f0)
                    {
                        F[i][u] = L[u][i];
                        L[u][i] = 0;
                        C[i][u] = 0;
                        fl[i] += F[i][u];
                        f0 -= F[i][u];
                    }
                    else
                    {
                        F[i][u] = f0;
                        fl[i] += f0;
                        L[u][i] -= f0;
                        f0 = 0;
                    }
                    Cap[u] = Cap[u] - fl[i];
                    if(Cap[u] == 0)
                    {
                        sint--;
                        E[u] = 0;
                        for(j = 1; j <= N; j++)
                            C[u][j] = L[u][j] = 0;
                    }
                }

            if(f0)
                flow -= f0;
    }
}

bool way(int nod)
{
    queue <int> Q;
    int i;
    Q.push(nod);
    memset(fl, 0, sizeof(fl));
    fl[nod] = 1;
    while(!Q.empty())
    {
        nod = Q.front();
        Q.pop();
        for(i = 1; i <= N; i++)
            if(C[nod][i] && !fl[i])
            {
                fl[i] = 1;
                Q.push(i);
                if(i == N)
                    return true;
            }
    }
    return fl[N];
}

int main()
{
    read();
    calc();
    int mini, i, nod, j;
    while(sint)
    {
        mini = 10000000;
        for(i = 1; i <= N; i++)
            if(E[i] && mini > Cap[i])
                mini = Cap[i], nod = i;
        if(way(nod))
        {
            flow += Cap[nod];
            Push( nod );
            Pull( nod );
        }
        else {
            sint--;
            E[nod] = 0;
            for(j = 1; j <= N; j++)
                C[nod][j] = L[nod][j] = L[j][nod] = C[j][nod] = 0;
        }
        if(E[nod])
        {
            sint--;
            E[nod] = 0;
            for(j = 1; j <= N; j++)
                C[nod][j] = L[nod][j] = 0;
        }
    }
    ofstream out ("maxflow.out");
    out << flow;
    return 0;
}