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

/*
 *
 */
using namespace std;
ifstream in;
int N, source, sink, idx;
char file[SIZE];
int C[Nmax][Nmax];
int d[Nmax], f[Nmax], Cv[Nmax], frecv[Nmax];
inline void read( int& x )
{
    while( file[idx] < '0' || file[idx] > '9' )
        if( ++idx == SIZE )
        {
            in.read( file, SIZE );
            idx=0;
        }
    x=0;
    while( file[idx] >= '0' && file[idx] <= '9' )
    {
        x=x*10+file[idx]-'0';
        if( ++idx == SIZE )
        {
            in.read( file, SIZE );
            idx=0;
        }
    }
}
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;
    in.open( "maxflow.in" );
    read(N);
    sink=N;
    source=1;
    for( read(M); M; --M )
    {
        read(x); read(y); read(C[x][y]);
    }
    ofstream out( "maxflow.out" );
    out<<MaxFlow()<<'\n';
    return EXIT_SUCCESS;
}