// CHAT GPT 4
#include <iostream>
#include <cstdio>
#include <vector>
#include <limits>
#include <queue>

using namespace std;

const int INF = numeric_limits<int>::max();

struct Edge {
    int to, capacity, flow, rev;
};

void add_edge(vector<vector<Edge>>& graph, int from, int to, int capacity) {
    graph[from].push_back({to, capacity, 0, (int)graph[to].size()});
    graph[to].push_back({from, 0, 0, (int)graph[from].size() - 1});
}

void push(vector<vector<Edge>>& graph, vector<int>& excess, int u, Edge& e) {
    int flow = min(excess[u], e.capacity - e.flow);
    e.flow += flow;
    graph[e.to][e.rev].flow -= flow;
    excess[e.to] += flow;
    excess[u] -= flow;
}

void relabel(vector<vector<Edge>>& graph, vector<int>& height, int u) {
    int min_height = INF;
    for (const auto& e : graph[u]) {
        if (e.capacity > e.flow) {
            min_height = min(min_height, height[e.to]);
        }
    }
    if (min_height < INF) {
        height[u] = min_height + 1;
    }
}

void discharge(vector<vector<Edge>>& graph, vector<int>& excess, vector<int>& height, vector<int>& current, int u) {
    while (excess[u] > 0) {
        if (current[u] == graph[u].size()) {
            relabel(graph, height, u);
            current[u] = 0;
        } else {
            Edge& e = graph[u][current[u]];
            if (e.capacity > e.flow && height[u] > height[e.to]) {
                push(graph, excess, u, e);
            } else {
                current[u]++;
            }
        }
    }
}

int max_flow(vector<vector<Edge>>& graph, int source, int sink) {
    int V = graph.size();
    vector<int> excess(V, 0), height(V, 0), current(V, 0);

    height[source] = V;
    excess[source] = INF;
    for (auto& e : graph[source]) {
        push(graph, excess, source, e);
    }

    queue<int> active;
    for (int u = 0; u < V; ++u) {
        if (u != source && u != sink && excess[u] > 0) {
            active.push(u);
        }
    }

    while (!active.empty()) {
        int u = active.front();
        active.pop();
        discharge(graph, excess, height, current, u);
        if (excess[u] > 0) {
            active.push(u);
        }
    }

    int max_flow = 0;
    for (const auto& e : graph[source]) {
        max_flow += e.flow;
    }
    return max_flow;
}

int main() {
    int n, m, x, y, z;
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);
    cin >> n >> m;
    vector <vector<Edge> > v(n);
    for(int i = 1; i <= m; i ++) {
        cin >> x >> y >> z;
        x--;
        y--;

        add_edge(v, x, y, z);
    }

    cout << max_flow(v, 0, n-1) << '\n';
    return 0;
}