//Algoritmul lui Ford Fulkerson
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int N , M ;

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

nod * L [ 1001 ] , * LR [ 1001 ] ; // lista de vecini respectiv lista reziduala

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->capacity = c ;
    p->flow = 0 ;
    p->next = L [a] ;
    L [a] = p ;

    p = new nod ;
    p->info = b ;
    p->capacity = c ;
    p->flow = -1 ; // oricum la Graful Rezidual nu conteaza
    p->next = LR [a] ;
    LR [a] = p ;
}

int viz [ 1001 ] , viz2 [ 1001] ;
int dest ; // destinatie
int minim ; // capacitate reziduala minima
int fluxmax ; // fluxul maxim cerut
bool sw = 1 ; // cat timp mai exista augmeting path

void DFSFindAugmentingPath ( nod * sursa )
{
    if ( minim > sursa->capacity )
            minim = sursa->capacity ;

    viz [ sursa->info ] = 1 ;

    for ( nod * p = LR [ sursa->info ] ; p != 0 ; p = p->next )
       {
           if ( viz [ p->info ] == 0 )
                    DFSFindAugmentingPath ( p ) ;

           if ( p->info == dest )
            {
                sw = 1 ;
                fluxmax += minim ;
                p->capacity -= minim ;
                if ( p->capacity == 0 )
                     {
                         nod * y = p ;
                         delete y ;
                     }
               // L [ sursa->info ] ->flow += minim ;
                if ( viz2 [ sursa->info ] == 0 )
                {
                    viz2 [ p->info ] = 1 ;
                    nod * q = new nod ;
                    q->info = sursa->info ;
                    q->capacity = minim ;
                    q->flow = -1 ;
                    q->next = LR [ p->info ] ;
                    LR [ p->info ] = q  ;
                }
                else
                {
                    LR [ p->info ]->capacity += minim ;
                }

                return ;
            }

           cout << sursa->info << " " ;

           LR [ sursa -> info ] ->capacity -= minim ;
          // L [ sursa->info ]->flow += minim ;
           if ( LR [ sursa->info ] ->capacity = 0 )
                     {
                         nod * y = LR [ sursa->info ] ;
                         LR [ sursa->info ] = y->next ;
                         delete y ;
                     }

          if ( viz2 [ sursa->info ] == 0 )
                {
                    viz2 [ p->info ] = 1 ;
                    nod * q = new nod ;
                    q->info = sursa->info ;
                    q->capacity = minim ;
                    q->flow = -1 ;
                    q->next = LR [ p->info ] ;
                    LR [ p->info ] = q  ;
                }
                else
                {
                    LR [ p->info ]->capacity += minim ;
                }

         return ;
       }

}

int main()
{
    Citire () ;
    dest = N ;
    Add ( 0 , 1 , 100000 ) ;

   while ( sw == 1 )
    {
        sw = 0 ;
        minim = 100001 ;
        DFSFindAugmentingPath ( LR [0] ) ;
        for ( int i = 0 ; i <= 1001 ; ++ i )
                        viz [i] = 0 ;

        cout << endl ;


    }

    fout << fluxmax ;
    return 0;
}