#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int oo = 200000;
int n, m, s;
vector < vector < pair < int, int > > > a;
vector < int > minime, drum;

void citire()
{
    ifstream f("maxflow.in");
    f >> n >> m;
    a.resize( n + 1 );
    for( int i = 0; i < m; ++i )
    {
        int x, y, z;
        f >> x >> y >> z;
        a[x].push_back( make_pair( y, z ) );
    }
    f.close();
}

void afisare()
{
    cout << endl;
    for( int i = 1; i <= n; ++i )
    {
        cout << "Nodul " << i << endl;
        for( int j = 0; j < a[i].size(); ++j )
            cout << a[i][j].first << " " << a[i][j].second << endl;
        cout << endl;
    }
    cout << endl << "Minime: " << endl;
    for( int i = 0; i < minime.size(); ++i )
        cout << minime[i] << " ";
    cout << endl << "Drum: " << endl;
    for( int i = 0; i < drum.size(); ++i )
        cout << drum[i] << " ";
    cout << endl;
}

void dfs( int nod )
{
    drum.push_back( nod );
    if( nod == n )
    {
        s += minime[ minime.size() - 1 ];
        for( int i = 0; i < drum.size() - 1; ++i )
        {
            for( int j = 0; j < a[ drum[i] ].size(); ++j )
                if( a[ drum[i] ][j].first == drum[ i + 1 ] )
                {
                    a[ drum[i] ][j].second -= minime[ minime.size() - 1 ];
                    break;
                }
        }
        drum.pop_back();
        for( int i = 1; i < minime.size(); ++i )
            minime[i] -= minime[ minime.size() - 1 ];
        return;
    }
    for( int i = 0; i < a[nod].size(); ++i )
        if( a[nod][i].second )
        {
            minime.push_back( max( 0, min( a[nod][i].second, minime[ minime.size() - 1 ] ) ) );
            dfs( a[nod][i].first );
            minime.pop_back();
        }
    drum.pop_back();
}

int main()
{
    citire();
    minime.push_back( oo );
    dfs( 1 );
    ofstream g("maxflow.out");
    g << s;
    g.close();
    return 0;
}