#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 5000;
const int NIL = -1;
const int INF = numeric_limits <int> :: max();

struct Edge
{
    int v;
    int cap;
    int next;
};

Edge G[2 * MAX_M];
int head[MAX_N];
int D[MAX_N];
int F[MAX_N + 1];

int ptr[MAX_N];
int father[MAX_N];
int currentPointer[MAX_N];

int Q[MAX_N];
int qStart, qEnd;

void addEdge(int u, int v, int cap, int pos)
{
    G[pos] = { v, cap, head[u] };
    head[u] = pos;
}

int main()
{
    ifstream in("maxflow.in");
    int N, M;

    in >> N >> M;

    memset( head, NIL, 4 * N );

    for ( int i = 0; i < M; i++ )
    {
        int u, v, cap;

        in >> u >> v >> cap;

        addEdge( u - 1, v - 1, cap, 2 * i );
        addEdge( v - 1, u - 1, 0, 2 * i + 1 );
    }

    in.close();

    // ISAP

    Q[0] = N - 1;
    qStart = 0;
    qEnd = 1;
    D[N - 1] = 1;

    while ( qStart != qEnd )
    {
        int u = Q[qStart++];

        for ( int i = head[u]; i != NIL; i = G[i].next )
        {
            int v = G[i].v;

            if ( !G[i].cap && D[v] == 0 )
            {
                D[v] = D[u] + 1;
                Q[qEnd++] = v;
            }
        }
    }

    for ( int i = 0; i < N; i++ )
        F[ D[i] ]++;

    memmove( currentPointer, head, 4 * N );

    int flow = 0;
    int u = 0;

    while ( D[u] <= N )
    {
        if ( u == N - 1 )
        {
            int minFlow = INF;

            while ( u != 0 )
            {
                minFlow = min( minFlow, G[ ptr[u] ].cap );
                u = father[u];
            }

            u = N - 1;

            while ( u != 0 )
            {
                G[ ptr[u] ].cap     -= minFlow;
                G[ ptr[u] ^ 1 ].cap += minFlow;
                u = father[u];
            }

            u = 0;

            flow += minFlow;
        }

        int i = currentPointer[u];

        while ( ( i != NIL ) && ( !G[i].cap || D[u] != D[ G[i].v ] + 1 ) )
            i = G[i].next;

        if ( G[i].cap > 0 && D[u] == D[ G[i].v ] + 1 )
        {
            ptr[ G[i].v ] = i;
            father[ G[i].v ] = u;
            currentPointer[u] = i;

            u = G[i].v;
        }
        else
        {
            int T = N;

            for ( i = head[u]; i != NIL; i = G[i].next )
                if ( G[i].cap > 0 )
                    T = min( T, D[ G[i].v ] );

            F[ D[u] ]--;

            if ( !F[ D[u] ] )
                break;

            D[u] = T + 1;

            F[ D[u] ]++;
            currentPointer[u] = head[u];

            if ( u != 0 )
                u = father[u];

        }
    }

    ofstream out("maxflow.out");
    out << flow << '\n';
    out.close();
    return 0;
}