#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 1000;
const int mmax = 5000;
const int inf = (1 << 30) - 1 + (1 << 30);

int ans;

struct muchie {
    int x, flux, cap, indop, nxt;

    muchie () {}
    muchie (int _x, int _flux, int _cap, int _indop) {
        x = _x, flux = _flux, cap = _cap, indop = _indop;
    }
} e[2 * mmax + 1];

int n, nrm;
int firste[nmax + 1], laste[nmax + 1];
int unde[nmax + 1];

int dist[nmax + 1];

void trage_muchie (int x, int y, int cap) {
    ++ nrm;

    e[nrm] = muchie(y, 0, cap, nrm + 1);
    if (firste[x] == -1) {
        firste[x] = nrm;
    } else {
        e[laste[x]].nxt = nrm;
    }
    laste[x] = nrm;

    ++ nrm;
    e[nrm] = muchie(x, 0, 0, nrm - 1);
    if (firste[y] == -1) {
        firste[y] = nrm;
    } else {
        e[laste[y]].nxt = nrm;
    }
    laste[y] = nrm;
}

bool bfs (int S) {
    for (int i = 1; i <= n; ++ i)
        dist[i] = -1;

    queue<int> q;
    q.push(S);
    dist[S] = 0;

    while (!q.empty()) {
        int x = q.front();
        q.pop();

        int eind = firste[x];
        while (eind != -1) {
            if (dist[e[eind].x] == -1 && e[eind].flux < e[eind].cap) {
                dist[e[eind].x] = dist[x] + 1;
                q.push(e[eind].x);
            }

            eind = e[eind].nxt;
        }
    }

    return dist[n] != -1;
}

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

    if (f == 0)
        return 0;

    while (unde[nod] != -1) {
        int shp = 0;
        int inde = unde[nod];

        if (dist[e[inde].x] == dist[nod] + 1 && (shp = dfs(e[inde].x, min(f, e[inde].cap - e[inde].flux)))) {
            e[inde].flux += shp;
            e[e[inde].indop].flux -= shp;
            return shp;
        }

        unde[nod] = e[inde].nxt;
    }

    return 0;
}

bool dinic_step () {
    if (bfs(1) == 0)
        return 0;

    bool ok = 0;
    int new_flow = 0;

    for (int i = 1; i <= n; ++ i)
        unde[i] = firste[i];

    while ((new_flow = dfs(1, inf))) {
        if (new_flow) {
            ok = 1;
            ans += new_flow;
        }
    }

    return ok;
}

int main () {
    int m;

    fin >> n >> m;

    for (int i = 1; i <= n; ++ i)
        firste[i] = -1;

    for (int i = 1; i <= m; ++ i) {
        int x, y, z;
        fin >> x >> y >> z;
        trage_muchie(x, y, z);
    }

    for (int i = 1; i <= n; ++ i)
        e[laste[i]].nxt = -1;

    while (dinic_step()) {
    }

    fout << ans << "\n";

    fin.close();
    fout.close();
    return 0;
}