#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

vector < vector < int > > capacity;
vector < vector < int > > residual;
vector < vector < int > > sentFlow;
vector < bool > viz;

int n, m;
vector < int > road;
bool DFS(int node = 0) {
    road.push_back(node);
    viz[node] = true;

    if (node == n - 1) {
        return true;
    }
    for (int i = 0; i < n; ++i) {
        if (viz[i] == false && (sentFlow[node][i] < capacity[node][i] || residual[node][i])) {
            if (DFS(i)) {
                return true;
            }
        }
    }
    road.pop_back();
    return false;
}

int main() {
    ios::sync_with_stdio(false);

    fin >> n >> m;

    capacity.resize(n);
    for (auto &x: capacity) x.resize(n);

    for (int i = 0; i < m; ++i) {
        int a, b, c; 
        fin >> a >> b >> c;
        --a; --b;

        capacity[a][b] += c;
    }

    int totalFlow = 0;
    residual.resize(n);
    sentFlow.resize(n);
    viz.resize(n);
    for (auto &x: residual) x.resize(n);
    for (auto &x: sentFlow) x.resize(n);
    while (DFS()) {
        int maxFlow = INT_MAX;
        for (int i = 1; i < (int)road.size(); ++i) {
            int prev = road[i - 1];
            int now = road[i];
            assert(prev >= 0 && prev < n);
            assert(now >= 0 && now < n);
            maxFlow = min(maxFlow, max(capacity[prev][now] - sentFlow[prev][now], residual[prev][now]));
        }
        for (int i = 1; i < (int)road.size(); ++i) {
            int prev = road[i - 1];
            int now = road[i];
            assert(prev >= 0 && prev < n);
            assert(now >= 0 && now < n);
            if (capacity[prev][now] - sentFlow[prev][now] >= residual[prev][now]) {
                sentFlow[prev][now] += maxFlow;
                residual[now][prev] += maxFlow;
            } else {
                residual[prev][now] -= maxFlow;
                sentFlow[now][prev] -= maxFlow;
            }
        }
        totalFlow += maxFlow;
        while (!road.empty()) {
            road.pop_back();
        }
        viz.assign(n, false);
    }

    fout << totalFlow;
    return 0;
}