#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e3;

int flow[NMAX + 1][NMAX + 1];
vector <int> edges[NMAX + 1];
int p[NMAX + 1];

int s, d, n;

bool bfs() {
    queue <int> q;
    for ( int i = 1; i <= n; i ++ ) p[i] = 0;
    p[s] = -1;
    q.push( s );
    while ( !q.empty() ) {
        int node = q.front();
        q.pop();
        for ( auto i : edges[node] ) {
            if ( flow[node][i] > 0 && !p[i] ) {
                p[i] = node;
                q.push( i );
            }
        }

    }
    return ( p[d] != 0 );
}
int main() {
    ifstream fin( "maxflow.in" );
    ofstream fout( "maxflow.out" );
    int m, a, b, c, i, totalflow = 0;
    fin >> n >> m;

    for ( i = 0; i < m; i ++ ) {
        fin >> a >> b >> c;
        flow[a][b] = c;
        if ( !flow[b][a] ) {
            edges[a].push_back( b );
            edges[b].push_back( a );
        }
    }

    for ( i = 1; i <= n; i ++ ) {
        random_shuffle( edges[i].begin(), edges[i].end() );
    }

    totalflow = 0;
    s = 1;
    d = n;
    while ( bfs() ) {
        for ( auto node : edges[d] ) {
            if ( flow[node][d] <= 0 || !p[node] ) continue;
            int maxflow = flow[node][d];
            for ( i = node; i != s; i = p[i] ) {
                maxflow = min( maxflow, flow[p[i]][i] );
            }
            totalflow += maxflow;

            flow[node][d] -= maxflow;
            flow[d][node] += maxflow;
            for ( i = node; i != s; i = p[i] ) {
                flow[p[i]][i] -= maxflow;
                flow[i][p[i]] += maxflow;
            }
        }
    }
    fout << totalflow;
    return 0;
}