#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int inf= 1<<30;
const int nmax= 1005;

int n, m;
int c[nmax+1][nmax+1], r[nmax+1][nmax+1], p[nmax+1];

vector <int> v[nmax+1];

int bfs(  ) {
    queue <int> q;
    for ( ; !q.empty(); q.pop() ) ;
    for ( int i= 1; i<=n; ++i ) {
        p[i]= 0;
    }

    for ( q.push(1); !q.empty(); q.pop() ) {
        int x= q.front();
        for ( vector <int>::iterator it= v[x].begin(); it!=v[x].end(); ++it ) {
            if ( p[*it]==0 && (c[x][*it]>0 || r[x][*it]>0) ) {
                p[*it]= x;
                q.push(*it);

                if ( *it==n ) {
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main(  ) {
    int sol= 0;
    fin>>n>>m;
    for ( int i= 1, x, y, z; i<=m; ++i ) {
        fin>>x>>y>>z;
        v[x].push_back(y);
        c[x][y]= z;
    }

    while ( bfs() ) {
        int fmin= inf;
        for ( int i= n; i!=1; i= p[i] ) {
            if ( c[p[i]][i]>0 ) {
                fmin= min(fmin, c[p[i]][i]);
            } else {
                fmin= min(fmin, r[p[i]][i]);
            }
        }
        sol+= fmin;

        for ( int i= n; i!=1; i= p[i] ) {
            if ( c[p[i]][i]>0 ) {
                if ( r[i][p[i]]==0 ) {
                    v[i].push_back(p[i]);
                }
                r[i][p[i]]+= fmin;
                c[p[i]][i]-= fmin;
            } else {
                r[p[i]][i]-= fmin;
            }
        }
    }

    fout<<sol<<"\n";

    return 0;
}