/*
 * File:   main.cpp
 * Author: VirtualDemon
 *
 * Created on April 15, 2010, 4:48 PM
 */
#include <queue>
#include <cstdlib>
#include <fstream>
#include <algorithm>
#define Nmax 1111

/*
 *
 */
using namespace std;
int N, source, sink;
int C[Nmax][Nmax];
int d[Nmax], f[Nmax], Cv[Nmax], frecv[Nmax];
inline void RBFS( void )
{
    int x, y;
    queue< int > Q;
    fill( d+1, d+N, N );
    frecv[N]=N-1;
    frecv[0]=1;
    for( Q.push(sink); !Q.empty(); )
    {
        x=Q.front(); Q.pop();
        for( y=1; y <= N; ++y )
            if( N == d[y] && C[y][x] > 0  )
            {
                --frecv[N];
                d[y]=d[x]+1;
                ++frecv[d[y]];
                Q.push(y);
            }
    }
}
inline int Augment( void )
{
    int x=sink, c=C[f[x]][x];
    for( x=f[x]; source != x; x=f[x] )
        c=min( c, C[f[x]][x] );
    for( x=sink; source != x; x=f[x] )
    {
        C[f[x]][x]-=c;
        C[x][f[x]]+=c;
    }
    return c;
}
inline bool Retreat( int& x )
{
    if( 1 == frecv[d[x]] )
        return false;
    int i, min=N-1;
    for( i=1; i <= N; ++i )
        if( C[x][i] > 0 && d[i] < min )
            min=d[i];
    --frecv[d[x]];
    d[x]=1+min;
    ++frecv[d[x]];
    if( source != x )
        x=f[x];
    return true;
}
inline int MaxFlow( void )
{
    int flow=0, x, i;
    RBFS();
    fill( Cv+1, Cv+N+1, 1 );
    for( x=source; d[source] < N; )
    {
        for( i=Cv[x]; i <= N; ++i )
            if( C[x][i] > 0 && d[x] == d[i]+1 )
                break;
        if( i <= N )
        {
            f[i]=x;
            Cv[x]=i;
            x=i;
            if( sink == x )
            {
                flow+=Augment();
                x=source;
            }
        }
        else {
                Cv[x]=1;
                if( !Retreat(x) )
                    return flow;
            }
    }
    return flow;
}
int main( void )
{
    int M, x, y;
    ifstream in( "maxflow.in" );
    in>>N>>M;
    sink=N;
    source=1;
    for( ; M; --M )
    {
        in>>x>>y;
        in>>C[x][y];
    }
    ofstream out( "maxflow.out" );
    out<<MaxFlow()<<'\n';
    return EXIT_SUCCESS;
}