#include <fstream>
#include <vector>

using namespace std;

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

const int N_MAX = 2000;
const int INF = 1000000000;

int N, M, Source, Dest;
vector<int> Edges[N_MAX + 1];
int Capacity[N_MAX + 1][N_MAX + 1], Flow[N_MAX + 1][N_MAX + 1];
int Q[N_MAX + 1], T[N_MAX + 1];
bool viz[N_MAX + 1];

bool BFS() {
    //initializare
    int st = 1, dr = 0;
    Q[++dr] = Source;
    for ( int i = 1; i <= N; ++i )
        viz[i] = false;
    viz[Source] = true;

    while ( st <= dr ) {
        int x = Q[st++];
        if ( x == Dest ) // excludem destinatia pt optimizare: amelioram astfel mai multe drumuri din aceeasi parcurgere BFS
            continue;

        for ( auto y : Edges[x] ) {
            if ( viz[y] || Capacity[x][y] == Flow[x][y] ) //se face parcurgerea doar prin arcele nesaturate
                continue;

            viz[y] = true;
            Q[++dr] = y;
            T[y] = x;  //tatal lui y in arborele BFS
        }
    }

    return viz[Dest];  //daca BFS returneaza 0, inseamna ca nu am vizitat destinatia, deci nu mai avem ce ameliora, avem flux maxim
}

int main() {
    int x, y, c;
    in >> N >> M;
    Source = 1, Dest = N;
    for ( int i = 1; i <= M; ++i ) {
        in >> x >> y >> c;
        Edges[x].push_back( y );
        if( !Capacity[y][x] ) {
            Capacity[x][y] = c;
            Capacity[y][x] = 0;
            Edges[y].push_back( x );
        } else {    //artrificiu pentru a nu avea arcuri antiparalele
            Edges[x].push_back( ++N );
            Edges[N].push_back( x );
            Capacity[x][N] = c;
            Capacity[N][x] = 0;
            Edges[N].push_back( y );
            Edges[y].push_back( N );
            Capacity[N][y] = c;
            Capacity[y][N] = 0;
        }
    }

    int maxflow = 0;                                            //pornim cu fluxul 0 initial
    while ( BFS() )                                             //la fiecare pas cautam un lant de ameliorare (formate din arce nesaturate), care exclude destinatia
        for ( auto x : Edges[Dest] ) {                          //luam frunzele arborelui BFS, care au arce direct in destinatie
            if ( !viz[x] || Flow[x][Dest] == Capacity[x][Dest] ) //trecem doar prin arborele BFS
                continue;

            int flowgap = INF;
            T[Dest] = x;
            for ( x = Dest; x != Source; x = T[x] ) //parcurgem invers lantul de ameliorare si determinam capacitatea reziduala minima
                flowgap = min( flowgap, Capacity[T[x]][x] - Flow[T[x]][x] );

            //amelioram fluxul lantului
            for ( x = Dest; x != Source; x = T[x] ) {
                Flow[T[x]][x] += flowgap;  //se creste fluxul pe arcele retelei de transport
                Flow[x][T[x]] -= flowgap;  //se scade fluxul pe arcele grafului rezidual
            }
            maxflow += flowgap;
        }

    out << maxflow;

    return 0;
}