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

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

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

void nivelare(int nod);
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(z, maxim);
        G[x].push_back(y);
        h[{x, y}] = z;
        if (h[{x, y}])
            G[y].push_back(x);
    }

    prag = (1 << (int)(log2(maxim)));
    nivelare(1);
    while (prag)
    {
        x = 1;
        int cnt = 0;
        while (x)
        {
            for (int i = 0; i <= n; i++) viz[i] = 0;
            x = DFS(1, INT_MAX);
            flow += x;
        }
        prag /= 2;
        nivelare(1);
    }
    fout << flow;
    return 0;
}

void nivelare(int nod)
{
    queue <int> Q;
    for (int i = 0; i <= n; i++) {viz[i] = 0; dead_end[i] = 0;}
    nivel[nod] = 0;
    viz[nod] = 1;
    Q.push(nod);
    while (!Q.empty())
    {
        int vf = Q.front();
        Q.pop();

        for (auto el : G[vf])
            if (viz[el] == 0 && h[{vf, el}])
            {
                Q.push(el);
                nivel[el] = nivel[vf] + 1;
                viz[el] = 1;
            }
    }
}

int DFS(int nod, int minim)
{
    if (nod == n)
        return minim;

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