#include<fstream>
    #include<vector>
    #define MAX 1001
    #define pb push_back
    #define INF 110001
    using namespace std;
    int N ,M , nod , p[MAX] , c[MAX][MAX] , f[MAX][MAX], flow , q[MAX] , fmin;
    vector<int> g[MAX];
    bool viz[MAX];

    void citire();
    void solve();
    void tipar();
    bool BF();

    int main()
    {
        citire();
        solve();
        tipar();
        return 0;
    }

    void citire()
    {
        int x , y;
        ifstream f("maxflow.in");
        f>>N>>M;
        for( int i = 1 ; i <= M ; ++i )
            {
                f>>x>>y;
                f>>c[x][y];
                g[x].pb(y);
                g[y].pb(x);
            }
        f.close();
    }

    void solve()
    {

        while(BF())
        {
            fmin = INF;
            for(int nod = N ; nod != 1 ; nod = p[nod])
                fmin = min(fmin,c[p[nod]][nod] - f[p[nod]][nod]);
            for(int nod = N ; nod!= 1 ; nod = p[nod])
            {
                f[p[nod]][nod] += fmin;
                f[nod][p[nod]] -=fmin;
            }
            flow +=fmin;
        }
    }

    bool BF()
    {
        int next;
        for(int i = 1 ; i <= N ; ++i )viz[i] = 0;
        q[0] = q[1] = viz[1] = 1;
        for(int i = 1 ; i <= q[0] ; ++i )
        {
            for(int j = 0 ; j < g[q[i]].size() ; ++j )
            {
                next = g[q[i]][j];
                if(viz[next] || f[q[i]][next] == c[q[i]][next])
                    continue;
                viz[next] = 1;
                q[++q[0]] = next;
                p[next] = q[i];
                if(next == N)
                    return 1;
            }
        }
        return 0;
    }

    void tipar()
    {
        ofstream fout("maxflow.out");
        fout<<flow;
        fout.close();
    }