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

/*
 *
 */
using namespace std;
int N, source, sink;
int C[Nmax][Nmax];
int d[Nmax], f[Nmax], numbs[Nmax], CurrentV[Nmax];
vector< int > G[Nmax];
vector< int >::const_iterator it, iend;
inline void RBFS( void )
{
    int x;
    queue< int > Q;
    for( x=1; x <= N; ++x )
        d[x]=N;
    numbs[N]=N-1;
    d[sink]=0;
    numbs[0]=1;
    for( Q.push(sink); !Q.empty(); )
    {
        x=Q.front(); Q.pop();
        for( it=G[x].begin(), iend=G[x].end(); it < iend; ++it )
            if( N == d[*it] && C[*it][x] > 0 )
            {
                --numbs[d[*it]];
                d[*it]=1+d[x];
                ++numbs[d[*it]];
                Q.push(*it);
            }
    }
}
inline int Augment( void )
{
    int x, c=oo;
    for( x=sink; 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 == numbs[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];
    --numbs[d[x]];
    d[x]=1+min;
    ++numbs[d[x]];
    if( source != x )
        x=f[x];
    return true;
}
inline int MaxFlow( void )
{
    int flow=0, x, i;
    RBFS();
    for( x=1; x <= N; ++x )
        CurrentV[x]=1;
    for( x=source; d[source] < N; )
    {
        for( i=CurrentV[x]; i <= N; ++i )
            if( C[x][i] > 0 && d[x] == d[i]+1 )
                break;
        if( i <= N )
        {
            f[i]=x;
            CurrentV[x]=i;
            x=i;
            if( x == sink )
            {
                flow+=Augment();
                x=source;
            }
        }
        else {
                CurrentV[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];
        G[y].push_back(x);
    }
    ofstream out( "maxflow.out" );
    out<<MaxFlow()<<'\n';
    return EXIT_SUCCESS;
}