#include <cassert>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

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

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

queue <int> q;
vector <int> v[nmax+1];

int bfs(  ) {
    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();
        if ( x==n ) {
            return 1;
        }

        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);
            }
        }
    }
    return 0;
}

int main(  ) {
    assert( freopen("maxflow.in", "r", stdin));
    assert( freopen("maxflow.out", "w", stdout));

    int sol= 0;
    assert( scanf("%d%d", &n, &m) );
    for ( int i= 1, x, y, z; i<=m; ++i ) {
        assert( scanf("%d%d%d", &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;
            }
        }
    }

    printf("%d\n", sol);

    return 0;
}