#include <bits/stdc++.h>
#define NMAX 1008

using namespace std;
ifstream fin ("maxflow.in");
ofstream fout ("maxflow.out");

int n, m, flow, maxim;
long long prag;
bool viz[NMAX];
map < pair <int, int>, int> h;
vector <int> G[NMAX];

int DFS(int nod, int minim);

int main()
{
    int x, y, z;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        maxim = max(maxim, z);
        G[x].push_back(y);
        h[{x, y}] = z;
        if (h[{y, x}] == 0)
            G[y].push_back(x);
    }
    prag = (1 << ((int)log2(maxim)));
    x = 1;
    while (prag)
    {
        for (int i = 0; i <= n; i++) viz[i] = 0;
        x = DFS(1, INT_MAX);
        flow += x;
        if (x == 0)
            prag /= 2;
    }
    fout << flow;
    return 0;
}

int DFS(int nod, int minim)
{
    viz[nod] = 1;
    if (nod == n)
        return minim;

    for (auto vf : G[nod])
        if (viz[vf] == 0 && h[{nod, vf}] >= prag)
        {
            int x = DFS(vf, min(minim, h[{nod, vf}]));
            if (x > 0)
            {
                h[{nod, vf}] -= x;
                h[{vf, nod}] += x;
                return x;
            }
        }
    return 0;
}