#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define DIMN 1005
#define INF 1000000000
FILE *f=fopen("maxflow.in","r"), *g=fopen("maxflow.out","w");

using namespace std;

int N, M, S, T, F[DIMN][DIMN], C[DIMN][DIMN], viz[DIMN];        // F[i][j] = fluxul de la i la j, C[i][j] = capacitatea
vector <int> v[DIMN];

struct Arbore{ int nod, tata, flux; } Q[DIMN];

void Citire(){

    int i, x, y;

    fscanf(f,"%d %d\n",&N,&M);
    S = 1; T = N;

    for(i=1;i<=M;i++){

        fscanf(f,"%d %d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(-x);                                     // arcele inverse sunt puse cu semn schimbat
        fscanf(f,"%d\n",&C[x][y]);

    }

}

bool BFS(){

    int i, k1, k2, nod, vnod, flux, fluxNOU, preT, fluxT;                   // preT = tata lui T
    fluxT = 0;                                                              // fluxT = fluxul maxim catre T
    memset(viz,0,sizeof(viz));

    k1 = k2 = 1;
    Q[1].nod = S;
    Q[1].flux = INF;
    Q[1].tata = 0;
    viz[1] = 1;

    while( k1 <= k2 ){

        nod = abs(Q[k1].nod);
        flux = Q[k1].flux;

        for(i=0;i<v[nod].size();i++){

            vnod = v[nod][i];

            if( vnod < 0 ) fluxNOU = min( flux, F[abs(vnod)][nod] );        // ARC INVERS
            else fluxNOU = min( flux, C[nod][vnod] - F[nod][vnod] );        // ARC DIRECT

            if( vnod == T ){                                                // Daca am ajuns la nodul final si e un drum cu cap reziduala mai mare, il luam
                if( fluxT < fluxNOU ){
                    fluxT = fluxNOU;
                    preT = k1;                                              // Tin minte de unde din Q am venit
                }
            }
            else if( viz[abs(vnod)] == 0 && fluxNOU > 0 ){                  // E nevizitat si fluxul a ramas pozitiv
                k2 ++;
                Q[k2].nod = vnod;
                Q[k2].flux = fluxNOU;
                Q[k2].tata = k1;
                viz[abs(vnod)] = 1;
            }

        }

        k1 ++;

    }

    if( fluxT == 0 )        // Nu am gasit nimic de marit
        return 0;

    k2 ++;                  // Pun la finalul cozii datele despre T, ca sa-mi fie mai usor mai jos
    Q[k2].nod = T;
    Q[k2].flux = fluxT;
    Q[k2].tata = preT;

    i = k2;
    while( i > 0 ){

        vnod = Q[i].nod;
        nod = Q[ Q[i].tata ].nod;

        if( vnod < 0 ) F[abs(vnod)][nod] -= fluxT;
        else F[abs(nod)][vnod] += fluxT;

        i = Q[i].tata;

    }

    return 1;

}

void FordFulkerson(){

    int i, flux;

    while( BFS() );         // Cat timp fluxul se modifica

    flux = 0;
    for(i=0;i<v[S].size();i++)
        flux += F[S][v[S][i]];

    fprintf(g,"%d\n",flux);

}

int main(){

    Citire();
    FordFulkerson();

return 0;
}