#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define INF 1e9

using namespace std;

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

vector<vector<int>> la, laInvers, c, f;
vector<int> tata, viz;

bool bfs(int N) {
    tata = viz = vector<int>(N + 1, 0);
    queue<int> q;
    q.push(1);
    viz[1] = 1;

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

        for (auto& vecin : la[crt]) {
            if (viz[vecin] == 0 && c[crt][vecin] - f[crt][vecin] > 0) {
                q.push(vecin);
                viz[vecin] = 1;
                tata[vecin] = crt;

                if (vecin == N) {
                    return true;
                }
            }
        }

        for (auto& vecin : laInvers[crt]) {
            if (viz[vecin] == 0 && f[vecin][crt] > 0) {
                q.push(vecin);
                viz[vecin] = 1;
                tata[vecin] = -crt;

                if (vecin == N) {
                    return true;
                }
            }
        }
    }

    return false;
}

int main() {
    int N, M;
    fin >> N >> M;

    la = laInvers = vector<vector<int>>(N +1);
    c = f = vector<vector<int>>(N + 1, vector<int>(N + 1, 0));
    for (int i = 0; i < M; i++) {
        int x, y, w;
        fin >> x >> y >> w;

        la[x].push_back(y);
        laInvers[y].push_back(x);
        c[x][y] = w;
    }

    int maxflow = 0;
    while (bfs(N)) {
        int iP = INF;

        int crt = N;
        while (crt != 1) {
            if (tata[crt] > 0) {
                if (c[tata[crt]][crt] - f[tata[crt]][crt] < iP) {
                    iP = c[tata[crt]][crt] - f[tata[crt]][crt];
                }
                crt = tata[crt];
            }

            if (tata[crt] < 0) {
                if (f[crt][-tata[crt]] < iP) {
                    iP = f[crt][-tata[crt]];
                }
                crt = -tata[crt];
            }
        }

        crt = N;
        while (crt != 1) {
            if (tata[crt] > 0) {
                f[tata[crt]][crt] += iP;
                crt = tata[crt];
            }

            if (tata[crt] < 0) {
                f[crt][-tata[crt]] -= iP;
                crt = -tata[crt];
            }
        }
        maxflow += iP;
    }

    fout << maxflow << endl;
    return 0;
}