/// Dinic's algorithm with Capacity Scaling - Solutie de 100 de puncte, Complexitate: O(log(C) * m * n)   C - Capacitatea maxima a unei muchii, m - Nr. de muchii, n - Nr. de noduri
/// !De incercat de facut Capacity Scaling la nivelare, nu la cautarea drumului de crestere!
#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;

map < pair < int, int >, int > h;
vector < int > v[MAX], dead_ends;
int n, prag, nvl[MAX];
bool dead_end[MAX];

void nivelare(int nod);
int dfs(int nod, int minn);

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

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

    nivelare(1);
    while(nvl[n] != 0)
    {
        while(prag != 0)
        {
            x = dfs(1, INT_MAX);
            if(x != 0) r += x;
            else
            {
                prag /= 2;
                for(int it:dead_ends) dead_end[it] = 0;
                dead_ends.clear();
            }
        }
        nivelare(1);
    }
    cout << r;

    return 0;
}

void nivelare(int nod)
{
    int maxx = 0;

    queue < int > q;
    for(int i = 1; i <= n; i++) nvl[i] = 0, dead_end[i] = 0;

    nvl[nod] = 1, q.push(nod);
    while(q.empty() == 0)
    {
        nod = q.front(), q.pop();
        for(int it:v[nod])
        {
            if(nvl[it] == 0 || nvl[it] == nvl[nod] + 1) maxx = max(maxx, h[{nod, it}]);
            if (nvl[it] == 0 && h[{nod, it}] > 0)
            {
                nvl[it] = nvl[nod] + 1;
                q.push(it);
            }
        }
    }

    prag = (1<<int(log2(maxx)));
}

int dfs(int nod, int minn)
{
    if(nod == n) return minn;

    for(int it:v[nod]) if(nvl[it] == nvl[nod] + 1 && dead_end[it] == 0 && h[{nod, it}] >= prag)
        {
            int x = dfs(it, min(minn, h[{nod, it}]));
            if(x > 0)
            {
                h[{nod, it}] -= x;
                h[{it, nod}] += x;
                return x;
            }
            else dead_end[it] = 1, dead_ends.push_back(it);
        }

    return 0;
}