//Algoritmul Edmonds-Karp ( Ford-Fulkerson cu BFS )
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin ("maxflow.in") ;
ofstream fout ("maxflow.out") ;

int N , M ;

struct nod
{
    nod * next ;
    int info ;
} ;

nod * L [ 1001 ] ;
int capacity [1001][1001] ;

void Add ( int a , int b , int c ) ;
void Citire ()
{
    fin >> N >> M ;
    int a , b , c ;
    while ( M >= 1 )
    {
        fin >> a >> b >> c ;
        Add ( a , b , c ) ;
        -- M ;
    }
}

void Add ( int a , int b , int c )
{
    nod * p = new nod ;
    p->info = b ;
    p->next = L [a] ;
    L [a] = p ;
    capacity [a][b] = c ;

    p = new nod ;
    p->info = a ;
    p->next = L [b] ;
    L [b] = p ;
    // capacity [b][a] = 0 ;
}

int fluxmax ;
int tata [ 1001 ] ;
bool viz [ 1001 ] ;

void update()
{

     int minim = 100002 , fiu = N ;

    while ( fiu != 1 )
    {
        minim = min ( minim , capacity [ tata [ fiu ] ] [ fiu ] ) ;
        fiu = tata [ fiu ] ;
    }

    fluxmax += minim ; // va fi suma fluxurilor minime gasite

    fiu = N ;

    while ( fiu != 1 )  // cat timp nu am ajuns la sursa ( in cazul nsotru nodul 1 )
    {

        capacity [ tata [ fiu ] ] [ fiu ] -= minim ;  // din muchia directa scad capacitatea reziduala ( minima )
        capacity [ fiu ] [ tata [ fiu ] ] += minim ;  // la muchia inversa o adaug
        fiu = tata [ fiu ];

    }


}

int coada [ 1001 ] ;
bool BFS()
{

    int pr = 1 , ul = 1 ;

    tata [ 1 ] = 0 ;
    memset ( viz , 0 , sizeof ( viz ) ) ;
    viz [ 1 ] = 1 ;
    coada [ pr ] = 1 ;

    bool augpath = 0 ; // AugmentingPath = drum in crestere , drumu de la sursa la destinatie care are capacitate reziduala > 0 ( minimul dintre capac )
    int el_coada ;

    while ( pr <= ul )
    {
        el_coada = coada [ pr ] , ++ pr ;

        for ( nod * p = L [ el_coada ] ; p != 0 ; p = p->next )
            if ( capacity [ el_coada ] [ p->info ] > 0 && viz [ p->info ] == 0 ) // am gasit o capacitate > 0 .. merg pe muchia ( el_coada , p->info )
            {

                viz [ p->info ] = 1 ;
                tata [ p->info ] = el_coada ;
                coada [ ++ ul ] = p->info ;

                if ( p->info == N )  // am atins nodul destinatie ?
                  {
                    update() ;
                    augpath = 1 ; // am gasit drumu in crestere
                    viz [ N ] = 0 ; // devizitez nodul destinatie pentru a mai putea fi atins iar
                    -- ul ; // si il scot din coada
                  }

            }

    }

    return augpath;
}

int main ()
{
    Citire () ;
    while ( BFS () ) {} // cat timp exista augmentingpaths
    fout << fluxmax ;
    return 0 ;
}