#include <bits/stdc++.h>
#include <fstream>
using namespace std;

// Edmonds-Karp algorithm implementation

std::vector<int> G[1001];
unordered_map<int, unordered_map<int, int>> capacity; // O(E) space
int flow[1001][1001];
int N, M;

void readInput() {
    ifstream f("maxflow.in");
    f >> N >> M;
    for (int i = 0; i < M; i++) {
        int x, y, c;
        f >> x >> y >> c;
        G[x].push_back(y);
        G[y].push_back(x);  // Add reverse edge for residual graph
        capacity[x][y] += c;  // Handle multiple edges
    }
    f.close();
}

int bfs(const std::vector<int> G[], std::vector<bool>& visited, int s, int t, int flow[][1001]) {
    std::queue<std::pair<int, int>> q;
    q.push({s, INT_MAX});
    visited[s] = true;
    std::vector<int> parent(1001, -1);

    while (!q.empty()) {
        int u = q.front().first;
        int currFlow = q.front().second;
        q.pop();

        for (int v : G[u]) {
            if (!visited[v] && capacity[u][v] - flow[u][v] > 0) {
                visited[v] = true;
                parent[v] = u;
                int newFlow = std::min(currFlow, capacity[u][v] - flow[u][v]);
                if (v == t) {
                    // Update flows along the path
                    int cur = v;
                    while (cur != s) {
                        int prev = parent[cur];
                        flow[prev][cur] += newFlow;
                        flow[cur][prev] -= newFlow;
                        cur = prev;
                    }
                    return newFlow;
                }
                q.push({v, newFlow});
            }
        }
    }

    return 0;
}

int EdmondsKarp(const std::vector<int> G[], int source, int sink) {
    int maxFlow = 0;
    // gasim un drum de crestere (augmented path)
    std::vector<bool> visited(1001);
    // BFS pentru Edmonds-Karp
    while (true) {
        int F = bfs(G, visited, source, sink, flow);
        if (F == 0) break;  // Nu mai exista drum de crestere
        maxFlow += F;
        std::fill(visited.begin(), visited.end(), false);
    }
    return maxFlow;
}

int main() {
    readInput();
    int source = 1, sink = N;

    ofstream g("maxflow.out");
    g << EdmondsKarp(G, source, sink);
    g.close();
    return 0;
}