/*
    Vom utiliza algoritmul Edmonds–Karp pentru determinarea fluxului maxim -> O(N * M * M);
    Asadar, pentru gasirea unui drum, vom folosi BFS, insa vom aplica urmatoarea optimizare:
        - vom parcurge doar pana inainte de destinatie, adica vom merge pana in nodurile care au
          muchie cu N, dar nu si in N inclusiv
        - dupa ce am terminat de parcurs cu BFS si de actualizat vectorul de tati corespunzator,
          pentru fiecare nod X care are muchie cu N, vom actualiza capacitatile de pe drumul (1 - X)
    Astfel, dupa o singura parcurgere, vom ameliora mai multe drumuri.
 */

#include <bits/stdc++.h>

int flow_after_BFS (std::vector<std::vector<int>> &adj_list,
                    std::vector<std::vector<int>> &capacity,
                    std::vector<int> &previous) {

    int n = adj_list.size() - 1;
    std::vector<bool> sel(n + 1, false);
    std::queue<int> bf_queue;

    bf_queue.push(1);
    sel[1] = true;

    while (!bf_queue.empty()) {
        int current = bf_queue.front();
        bf_queue.pop();

        for (auto nbh : adj_list[current]) {
            if (!sel[nbh] && capacity[current][nbh] > 0 && nbh != n) {
                sel[nbh] = true;
                bf_queue.push(nbh);
                previous[nbh] = current;
            }
        }
    }

    int max_flow_possible = 0;
    for (auto nbh : adj_list[n]) {
        if (!sel[nbh]) continue;

        int current_path_flow = capacity[nbh][n];
        int current = nbh;
        while (current != 1) {
            current_path_flow = std::min(current_path_flow, capacity[previous[current]][current]);
            current = previous[current];
        }

        capacity[nbh][n] -= current_path_flow;
        capacity[n][nbh] += current_path_flow;
        current = nbh;
        while (current != 1) {
            capacity[previous[current]][current] -= current_path_flow;
            capacity[current][previous[current]] += current_path_flow;
            current = previous[current];
        }

        max_flow_possible += current_path_flow;
    }

    return max_flow_possible;
}

int get_max_flow(std::vector<std::vector<int>> adj_list, std::vector<std::vector<int>> capacity) {
    int n = adj_list.size() - 1;
    std::vector<int> previous(n + 1, -1);

    int total_max_flow = 0;
    int path_flow = flow_after_BFS(adj_list, capacity, previous);
    while (path_flow) {
        total_max_flow += path_flow;
        path_flow = flow_after_BFS(adj_list, capacity, previous);
    }

    return total_max_flow;
}

int main()
{
    std::ifstream fin("maxflow.in");
    std::ofstream fout("maxflow.out");

    int n, m;
    fin >> n >> m;

    std::vector<std::vector<int>> adj_list(n + 1);
    std::vector<std::vector<int>> capacity(n + 1, std::vector<int>(n + 1, 0));

    for (int i = 1; i <= m; ++i) {
        int node1, node2, edge_capacity;
        fin >> node1 >> node2 >> edge_capacity;

        adj_list[node1].push_back(node2);
        adj_list[node2].push_back(node1);
        capacity[node1][node2] += edge_capacity;
    }

    fout << get_max_flow(adj_list, capacity);

    return 0;
}