#include <stdio.h>
#include <iostream>
#include <queue>
#define dim 1005
#define inf 1100000000
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?x:-x)

using namespace std;


int n,m,s,d,mark[dim];
int C[dim][dim];
int F[dim][dim];
queue<int>Queue;


void read(void);
void ford(void);
void write(void);
int BFS(void);

int main(){

    read();
    ford();
    write();
    return 0;
}

void read(){

    FILE * fin = fopen("maxflow.in","r");

    int i,x,y,c;

    fscanf(fin,"%d %d", &n, &m);

    for(i=0;i<m;i++){
        fscanf(fin,"%d %d %d", &x, &y, &c);
        C[x][y] = c;
    }
    s = 1;
    d = n;
}


void ford(){

    int i,a,b,lg,v;
    int L[dim];

    do{
        for(i=1;i<=n;i++)
            mark[i] = 0;

        if(BFS()) return ;

        L[0]=d;
        lg = 0;
        a=b=inf;

        while(L[lg] != s){
            ++lg;
            L[lg] = abs(mark[ L[lg-1] ]);

            if(mark[ L[lg-1] ] > 0)
                a = min(a,C[ L[lg] ][ L[lg-1] ] - F[ L[lg] ][ L[lg-1] ]);
            else if(mark[ L[lg-1] ] < 0)
                b = min(b,F[ L[lg-1] ][ L[lg] ]);
        }

        v = min(a,b);

        for(i=lg;i>0;i--)
            if(mark[ L[i-1] ] > 0)
                F[ L[i] ][ L[i-1] ]+=v;
            else
                F[ L[i-1] ][ L[i] ]-=v;
    }while(1);
}


void write(){


    FILE * fout = fopen("maxflow.out","w");

    unsigned long long vf=0;

    for(int i=1;i<=n;i++)
        vf+= F[i][d];

    fprintf(fout,"%d\n",vf);

}

int BFS(){

    int p,u,i,x;
    Queue.push(s);
    mark[s] = 1;

    while(!Queue.empty()){
        x = Queue.front();
        Queue.pop();

        for(i=1;i<=n;i++)
            if(!mark[i])
                if(F[x][i] < C[x][i]){
                    mark[i] = x;
                    Queue.push(i);
                }else if(F[i][x] > 0){
                    mark[i] = -x;
                    Queue.push(i);
                }
    }
    return !mark[d];
}