#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];
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;
}

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;
    }
    /*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";
        }*/
    }
    fout<<sol<<"\n";

    return 0;
}