/// Edmonds-Karp algorithm with Capacity Scaling - Solutie de 70 de puncte, Complexitate: O(log(C) * m * n)   C - Capacitatea maxima a unei muchii, m - Nr. de muchii, n - Nr. de noduri
/// Atentie: In practica constanta este mare, si nu are rezultate f. bune
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 1005

using namespace std;

vector < int > v[MAX];
map < pair < int, int >, int > h;
int n, prag, prec[MAX];
bool viz[MAX];

int bfs(int nod);

int main()
{
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");
    int m, i, x, y, z, maxx = 0, r = 0;

    cin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        v[x].pb(y), h[{x, y}] = z, maxx = max(maxx, z);
        if(h[{y, x}] == 0) v[y].pb(x);
    }

    prag = (1<<int(log2(maxx)));
    while(prag != 0)
    {
        for(i = 1; i <= n; i++) viz[i] = 0;
        prec[1] = 0;
        x = bfs(1);

        if(x != 0) r += x;
        else prag /= 2;
    }
    cout << r;

    return 0;
}

int bfs(int nod)
{
    int minn = INT_MAX, i;

    queue < int > q;
    q.push(nod), viz[nod] = 1;
    while(q.empty() == 0)
    {
        nod = q.front(), q.pop();
        for(int it:v[nod]) if(viz[it] == 0 && h[{nod,it}] >= prag)
            {
                prec[it] = nod;
                if(it == n)
                {
                    i = n;
                    while(prec[i] != 0)
                    {
                        minn = min(minn, h[{prec[i], i}]);
                        i = prec[i];
                    }

                    i = n;
                    while(prec[i] != 0)
                    {
                        h[{prec[i], i}] -= minn;
                        h[{i, prec[i]}] += minn;
                        i = prec[i];
                    }

                    return minn;
                }
                else q.push(it), viz[it] = 1;
            }
    }

    return 0;
}