#include <fstream>
#include <vector>
#include <queue>
#include <algorithm> // pentru std::fill și std::min

using namespace std;

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

const int INF = 1e9;

// Folosim vectori globali pentru a evita alocarea repetată, 
// dar îi redimensionăm în main.
int N, M;
vector<vector<int>> adj;      // Lista de adiacență
vector<vector<int>> capacity; // Matricea de capacități

// Funcția BFS primește vectorul de părinți prin referință (&) pentru a-l modifica
bool bfs(int s, int t, vector<int>& parent) {
    // În loc de memset, folosim fill din C++
    fill(parent.begin(), parent.end(), -1);
    
    queue<int> q;
    q.push(s);
    parent[s] = -2; // Marcăm sursa vizitată (valoare diferită de -1)

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

        if (u == t) return true;

        for (int v : adj[u]) {
            // Verificăm dacă nu e vizitat și dacă avem capacitate reziduală
            if (parent[v] == -1 && capacity[u][v] > 0) {
                parent[v] = u;
                q.push(v);
            }
        }
    }
    return false;
}

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

    // Inițializare și redimensionare în stil C++
    // N + 1 pentru a folosi indicii de la 1 la N
    adj.resize(N + 1);
    
    // Matrice de (N+1) x (N+1) inițializată cu 0
    capacity.assign(N + 1, vector<int>(N + 1, 0));

    for (int i = 0; i < M; i++) {
        int u, v, c;
        f >> u >> v >> c;
        adj[u].push_back(v);
        adj[v].push_back(u); // Muchie inversă pentru graful rezidual
        capacity[u][v] += c; 
    }
    f.close();

    int max_flow = 0;
    vector<int> parent(N + 1); // Vectorul de tați

    // Cât timp BFS găsește un drum de creștere
    while (bfs(1, N, parent)) {
        int path_flow = INF;
        
        // 1. Aflăm fluxul minim pe drumul găsit (gâtuirea)
        // Mergem de la destinație înapoi spre sursă folosind vectorul parent
        for (int v = N; v != 1; v = parent[v]) {
            int u = parent[v];
            path_flow = min(path_flow, capacity[u][v]);
        }

        // 2. Actualizăm capacitățile (Graful Rezidual)
        for (int v = N; v != 1; v = parent[v]) {
            int u = parent[v];
            capacity[u][v] -= path_flow; // Scădem pe direcția înainte
            capacity[v][u] += path_flow; // Adăugăm pe direcția inversă
        }

        max_flow += path_flow;
    }

    g << max_flow;
    g.close();

    return 0;
}