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

// Ford Fulkerson algorithm implementation

std::vector<int> G[1001];
int capacity[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);
        capacity[x][y] += c;  // Handle multiple edges
        capacity[y][x] += 0;
    }
    f.close();
}

int dfs(const std::vector<int> G[], int capacity[][1001], std::vector<bool>& visited, int u, int t, int flow) {
    if (u == t) return flow;
    visited[u] = true;
    for (int v : G[u]) {
        if (!visited[v] && capacity[u][v] > 0) {
            int currFlow = std::min(flow, capacity[u][v]);
            int tempFlow = dfs(G, capacity, visited, v, t, currFlow);
            if (tempFlow > 0) {
                capacity[u][v] -= tempFlow;
                capacity[v][u] += tempFlow;
                return tempFlow;
            }
        }
    }
    return 0;
}

int FordFulkerson(const std::vector<int> G[], int capacity[][1001], int source, int sink) {
    int maxFlow = 0;
    // gasim un drum de crestere (augmented path)
    std::vector<bool> visited(1001);
    // DFS pentru Ford-Fulkerson
    while (true) {
        int flow = dfs(G, capacity, visited, source, sink, INT_MAX);
        if (flow == 0) break;  // Nu mai exista drum de crestere
        maxFlow += flow;
        std::fill(visited.begin(), visited.end(), false);
    }
    return maxFlow;
}

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

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