#include <fstream>
#include <vector>

using namespace std;

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

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];
bool uq[nmax+1];
int q[nmax+1], p[nmax+1];

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

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

int main(){
    int m;

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

        fin>>x>>y>>z;
        g[x].push_back(y);
        g[y].push_back(x);
        c[x][y]+=z;
    }

    while (bfs()){
        for (vector <int>::iterator it= g[n].begin(); it!=g[n].end(); ++it){
            if (uq[*it]&& c[*it][n]+r[*it][n]>0){
                p[n]= *it;               
                int cm= cmax, i;
                for (i= n; i!=1&& uq[p[i]]&& c[p[i]][i]+r[p[i]][i]>0; i= p[i]){
                    if (cm>c[p[i]][i]+r[p[i]][i]){
                        cm= c[p[i]][i]+r[p[i]][i];
                    }
                }

                if (i==1){
                    sol+= cm;
                    for (i= n; i!=1; i= p[i]){
                        c[p[i]][i]-= cm;
                        r[i][p[i]]+= cm;
                    }
                }
            }
        }
    }
    fout<<sol<<"\n";

    return 0;
}