#include<stdio.h>
#include<algorithm>
#include<vector>
#define MAXN 1005
#define MAXM 5005
#define MAXI 2000000000
using namespace std;
FILE *f=fopen("maxflow.in","r"), *g=fopen("maxflow.out","w");

int N, M, Flux = 0;
int C[MAXN][MAXN], F[MAXN][MAXN], viz[MAXN];
int Q[MAXN], T[MAXN], u, p;

vector <int> v[MAXN];

void Citire(){
int i, j, x, y, c;

    fscanf(f,"%d %d\n",&N,&M);
    for(i=1;i<=M;i++){

        fscanf(f,"%d %d %d\n",&x,&y,&c);
        v[x].push_back(y);
        v[y].push_back(x);
        C[x][y] = c;

    }

}

void InitVIZ(){
int i;

    for(i=1;i<=N;i++){
        viz[i] = 0;
        T[i] = 0;
        Q[i] = 0;
    }

}

int BFS( int S, int D ){
int x, y, i;

    InitVIZ();

    Q[1] = S;
    T[1] = 0;
    viz[S] = 1;

    p = 1; u = 1;

    while( p <= u ){

        x = Q[p];

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

            y = v[x][i];

            if( viz[y] == 0 && (C[x][y] - F[x][y] > 0) )
            {
                viz[y] = 1;
                Q[++u] = y;
                T[  y] = x;

            }
        }
        p++;
    }

    return viz[D];
}

void Rezolvare(){
int minim, U, x, y, OK;

    OK = 1;

    while( BFS(1,N) )

    for(int i=0;i<v[N].size();i++)
    {
        x = v[N][i];
        if( viz[x] == 0 || C[x][N] - F[x][N] == 0 )
            continue;

        minim = C[x][N] - F[x][N];

        if(minim==0)
            continue;

        //T[N] = x;       // Aflu minimul
        //Actualizam fluxul dintre x si N


        U = x;
        while( U != 1 ){

            minim = min( minim, C[T[U]][U] - F[T[U]][U] );
            U = T[U];
        }

        Flux += minim;

 F[x][N] += minim;
        F[N][x] -= minim;

        U = x;              // Actualizam fluxul
        while( U != 1 ){

            F[T[U]][U] += minim;
            F[U][T[U]] -= minim;

            U = T[U];
        }

    }

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

}

int main(){

    Citire();
    Rezolvare();

return 0;
}