#include <bits/stdc++.h>

using namespace std;

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

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

Edge l[2 * MAX_M];
int adj[MAX_N];
int D[MAX_N];
int ptr[MAX_N];
int Q[MAX_N];
int N;

void addEdge( int u, int v, int cap, int pos )
{
    l[pos].v = v;
    l[pos].cap = cap;
    l[pos].next = adj[u];
    adj[u] = pos;
}

bool BFS( const int &N )
{
    int qStart, qEnd;

    memset( D, NIL, N * sizeof(int) );
    qStart = 0;
    qEnd = 1;
    D[0] = 0;
    Q[0] = 0;
    while ( qStart != qEnd && D[N - 1] == NIL )
    {
        int u = Q[qStart++];

        for ( int i = adj[u]; i != NIL; i = l[i].next )
        {
            int v = l[i].v;
            if ( D[v] == NIL && l[i].cap )
            {
                D[v] = D[u] + 1;
                Q[qEnd++] = v;
            }
        }
    }
    return D[N - 1] != NIL;
}

int DFS( int u, int flow )
{
    if ( u == N - 1 )
        return flow;

    for ( ; ptr[u] != NIL; ptr[u] = l[ ptr[u] ].next )
    {
        int v = l[ ptr[u] ].v;

        if ( D[v] == D[u] + 1 && l[ ptr[u] ].cap )
        {
            int newFlow = min( flow, l[ ptr[u] ].cap );
            int pushed = DFS( v, newFlow );

            if ( pushed != 0 )
            {
                l[ ptr[u] ].cap     -= pushed;
                l[ ptr[u] ^ 1 ].cap += pushed;
                return pushed;
            }
        }
    }
    return 0;
}

int dinic( const int &N )
{
    int flow = 0;
    int pushed;

    while ( BFS( N ) )
    {
        for ( int i = 0; i < N; ++i )
            ptr[i] = adj[i];

        do
        {
            pushed = DFS( 0, INF );
            flow += pushed;

        } while ( pushed );
    }

    return flow;
}

int main()
{
    ifstream in("maxflow.in");
    ofstream out("maxflow.out");
    in.tie(0);
    ios_base::sync_with_stdio(0);
    int M;

    in >> N >> M;

    for ( int i = 0; i < N; ++i )
        adj[i] = NIL;

    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();

    out << dinic( N ) << '\n';
    out.close();
    return 0;
}