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

std::ifstream f("maxflow.in");
std::ofstream g("maxflow.out");

const int NMAX = 1000; // Nr maxim de noduri
int capacity[NMAX + 1][NMAX + 1];
int residual[NMAX + 1][NMAX + 1]; // Matricea capacitatilor reziduale
int parent[NMAX + 1]; // Vector pentru a reconstrui drumul augmentativ

int bfs(int source, int sink, int n) {
    std::fill(parent, parent + n + 1, -1);
    std::queue<std::pair<int, int>> q; // (nod curent, flux curent)
    q.push({source, INT_MAX});

    while (!q.empty()) {
        int current = q.front().first;
        int flow = q.front().second;
        q.pop();

        for (int next = 1; next <= n; ++next) {
            if (parent[next] == -1 && residual[current][next] > 0) {
                parent[next] = current;
                int new_flow = std::min(flow, residual[current][next]);
                if (next == sink) return new_flow;
                q.push({next, new_flow});
            }
        }
    }

    return 0;
}

int edmondsKarp(int source, int sink, int n) {
    std::memcpy(residual, capacity, sizeof(capacity));
    int max_flow = 0;

    while (true) {
        int flow = bfs(source, sink, n);
        if (flow == 0) break; // Nu mai exista drum s-t nesaturat

        max_flow += flow;

        // Actualizăm capacitatile reeziduale
        int current = sink;
        while (current != source) {
            int prev = parent[current];
            residual[prev][current] -= flow; // Scadem fluxul de pe muchia directa
            residual[current][prev] += flow; // Adaugam fluxul pe muchia inversa
            current = prev;
        }
    }

    return max_flow;
}

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

    // Citim graful
    for (int i = 1; i <= M; ++i) {
        int u, v, cap;
        f >> u >> v >> cap;
        capacity[u][v] += cap; // 1 2 3 apoi 1 2 2
    }

//    int source = 1, sink = N;

    g << edmondsKarp(1, N, N);

    return 0;
}