#include <cassert>
#include <cstdio>
#include <cstdlib>

#include <vector>

using namespace std;

const int nmax= 1000, cmax= 110000;

int n, sol;
vector <int> g[nmax+1];
int c[nmax+1][nmax+1], r[nmax+1][nmax+1];
int q[nmax+1], p[nmax+1], cq[nmax+1];

int bfs(){
    q[0]= 1; q[1]= 1;
    for (int i= 2; i<=n; ++i){
        cq[i]= 0;
    }
    cq[1]= cmax;

    for (int i= 1; i<=q[0]; ++i){
        int x= q[i];
        for (vector <int>::iterator it= g[x].begin(); it!=g[x].end(); ++it){
            if (!cq[*it]&& c[x][*it]+r[x][*it]>0){
                ++q[0];
                q[q[0]]= *it;
                p[*it]= x;
                cq[*it]= min(cq[x], c[x][*it]+r[x][*it]);
                
                if (*it==n){
                    i= q[0];
                    return 1;
                }
            }
        }
    }

    return 0;
}

char *buffer;

void read_int(int  &x){
    while (*buffer<'0'|| *buffer>'9'){
        ++buffer;
    }

    x= 0;
    while (*buffer>='0'&& *buffer<='9'){
        x= x*10+*buffer-'0';
        ++buffer;
    }
}

int main(){
    int m, fs;

    assert(freopen("maxflow.in", "r", stdin));
    assert(freopen("maxflow.out", "w", stdout));
    fseek(stdin, 0, SEEK_END);
    fs= ftell(stdin);
    buffer=(char*)malloc(fs);
    rewind(stdin);
    assert(fread(buffer, 1, fs, stdin));


    read_int(n); read_int(m);
    for (int i= 1; i<=m; ++i){
        int x, y, z;

        read_int(x); read_int(y); read_int(z); 
        g[x].push_back(y);
        g[y].push_back(x);
        c[x][y]+=z;
    }
    /*for (int i= 1; i<=n; ++i){
            for (int j= 1; j<=n; ++j){
                fout<<c[i][j]<<" ";
            }
            fout<<"\n";
        }*/

    int sol= 0;
    while (bfs()){
        //fout<<sol<<"\n";
        sol+= cq[n];
        for (int i= n; i!=1; i= p[i]){
            //fout<<i<<" ";
            c[p[i]][i]-= cq[n];
            r[i][p[i]]+= cq[n];
        }
        //fout<<"\n";
        /*for (int i= 1; i<=n; ++i){
            for (int j= 1; j<=n; ++j){
                fout<<c[i][j]<<" ";
            }
            fout<<"\n";
        }*/
    }
    printf("%d\n", sol);

    return 0;
}