#include <cstdio>
#include <cassert>
#include <cctype>
#include <cstring>
#include <vector>
#include <queue>
#include <climits>

class inputParser {

    static const unsigned int buffSize = 1 << 17;
    unsigned int pozBuff;
    FILE* fin;
    unsigned char* buffer;


    void getChar( unsigned char& ch ) {
        if ( pozBuff == buffSize ) {
            pozBuff = 0;
            assert( fread( buffer, sizeof( char ), buffSize, fin ) );
        }
        ch = buffer[ pozBuff++ ];
    }


public:
    explicit inputParser( const char* fileName ) {
        fin = fopen( fileName, "r" );
        assert( fin != nullptr );
        buffer = new unsigned char[buffSize];
        pozBuff = buffSize;
    }


    inputParser( const inputParser& dummy ) = delete;

    inputParser& operator=( const inputParser& dummy ) = delete;


    template < class intType >
    inputParser& operator>>( intType& nr ) {
        int sgn( 1 );
        unsigned char ch;
        nr = 0;
        getChar( ch );
        while ( isdigit( ch ) == 0 && ch != '-' )
            getChar( ch );
        if ( ch == '-' ) {
            sgn = -1;
            getChar( ch );
        }
        while ( isdigit( ch ) != 0 ) {
            nr = nr * 10 + ch - '0';
            getChar( ch );
        }
        nr *= sgn;
        return *this;
    }


    inputParser& operator>>( char& ch ) {
        unsigned char ch2;
        do {
            getChar( ch2 );
        } while ( isgraph( ch2 ) == 0 );
        ch = static_cast<char>(ch2);
        return *this;
    }


    inputParser& operator>>( unsigned char& ch ) {
        getChar( ch );
        do {
            getChar( ch );
        } while ( isgraph( ch ) == 0 );
        return *this;
    }


    ~inputParser() {
        fclose( fin );
        delete[] buffer;
    }

};

class outputParser {

    static const unsigned int buffSize = 1 << 17;
    unsigned int pozBuff;
    FILE* fout;
    unsigned char* buffer;


    void putChar( const unsigned char ch ) {
        if ( pozBuff == buffSize ) {
            pozBuff = 0;
            fwrite( buffer, sizeof( char ), buffSize, fout );
        }
        buffer[ pozBuff++ ] = ch;
    }


public:
    explicit outputParser( const char* fileName ) {
        fout = fopen( fileName, "w" );
        buffer = new unsigned char[buffSize];
        pozBuff = 0;
    }


    outputParser( const outputParser& dummy ) = delete;

    outputParser& operator=( const outputParser& dummy ) = delete;


    template < class intType >
    outputParser& operator<<( intType nr ) {
        if ( nr < 0 ) {
            putChar( '-' );
            nr = -nr;
        }
        int cif[20];
        int pozCif = 0;
        do {
            cif[ pozCif++ ] = nr % 10;
            nr /= 10;
        } while ( nr > 0 );
        while ( pozCif > 0 ) {
            unsigned char ch = cif[ --pozCif ] + '0';
            putChar( ch );
        }
        return *this;
    }

    outputParser& operator<<( char ch ) {
        putChar( ch );
        return *this;
    }

    outputParser& operator<<( unsigned char ch ) {
        putChar( ch );
        return *this;
    }

    ~outputParser() {
        fwrite( buffer, sizeof( char ), pozBuff, fout );
        delete[] buffer;
        fclose( fout );
    }
};

using namespace std;
const int nMax = 1001;
int flux[nMax][nMax];
int tata[nMax];
vector< int > v[nMax];

int bfs( int n ) {
    int minFlowN( 0 );
    memset( tata, 0, sizeof( tata ) );///reinitializam vectorul de tati, care va contine drumul de intoracere de la destinatie la sursa
    queue< pair< int, int > > q;
    q.push( { 1, INT_MAX } );   ///coada va retine nodul si fluxul maxim ce poate fi transmis din sursa pana in el
    tata[ 1 ] = -1;             ///pt a evita sa ne intoarcem in sursa
    while ( !q.empty() && tata[ n ] == 0 ) {    ///daca gasim un drum la destinatie, ne oprim
        int nod = q.front().first;
        int minFlow = q.front().second;
        q.pop();
        for ( auto& i:v[ nod ] ) {
            if ( !tata[ i ] && flux[ nod ][ i ] ) {///doar daca noul nod nu a fost vizitat si se mai poate ajunge in el
                tata[ i ] = nod;
                minFlowN = min( minFlow, flux[ nod ][ i ] );
                q.push( { i, minFlowN } );
                if ( i == n )
                    break;      ///daca am ajuns la destinatie, ne oprim si retinem fluxul maxim ce mai poate fi transmis
            }
        }
    }
    if ( tata[ n ] )
        return minFlowN;    ///returnam fluxul ce poate fi adaugam prin drumul gasit
    else    ///daca nu am ajuns la n, inseamna ca nu mai exista niciun drum
        return 0;
}

int maxflow( int n ) {
    int flow( 0 );
    int minFlow;
    while ( ( minFlow = bfs( n ) ) ) {  ///cat timp bfs gaseste un drum de la sursa la destinatie
        int nod = n;
        while ( tata[ nod ] != -1 ) {
            flux[ tata[ nod ] ][ nod ] -= minFlow;  ///scadem de pe muchia de ducere fluxul posibil
            flux[ nod ][ tata[ nod ] ] += minFlow;  ///si il adaugam la muchia de intoarcere
            nod = tata[ nod ];
        }
        flow += minFlow;    ///valoarea returnata de bfs se adauga fluxul maxim
    }
    return flow;
}

int main() {
    int n, m;
    inputParser fin( "maxflow.in" );
    outputParser fout( "maxflow.out" );
    fin >> n >> m;
    for ( int i = 0; i < m; i++ ) {
        int a, b, c;
        fin >> a >> b >> c;
        flux[ a ][ b ] = c;
        v[ a ].push_back( b );
        v[ b ].push_back( a );
    }
    fout << maxflow( n );
    return 0;
}