// Graph Representation: The graph is represented using an adjacency list (graph) and a capacity matrix (capacity).
// Breadth-First Search (BFS): The bfs function finds an augmenting path from the source to the sink and returns the flow of the path.
// Edmonds-Karp Algorithm: The edmondsKarp function repeatedly finds augmenting paths using BFS and updates the capacities until no more augmenting paths are found.
// Main Function: Reads the number of vertices and edges, constructs the graph, and calls the edmondsKarp function to find and print the maximum flow.


#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cstring>
#include <fstream>

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

const int MAXN = 1000;

vector<int> graph[MAXN];
int capacity[MAXN][MAXN];
int parent[MAXN];

bool bfs(int source, int sink) {
    memset(parent, -1, sizeof(parent));
    queue<pair<int, int>> q;
    q.push({source, INT_MAX});

    while (!q.empty()) {
        int current = q.front().first;
        int flow = q.front().second;
        q.pop();

        for (int next : graph[current]) {
            if (parent[next] == -1 && capacity[current][next] > 0) {
                parent[next] = current;
                int new_flow = min(flow, capacity[current][next]);
                if (next == sink) {
                    return new_flow;
                }
                q.push({next, new_flow});
            }
        }
    }

    return 0;
}

int edmondsKarp(int source, int sink) {
    int max_flow = 0;
    int new_flow;

    while (new_flow = bfs(source, sink)) {
        max_flow += new_flow;
        int current = sink;
        while (current != source) {
            int prev = parent[current];
            capacity[prev][current] -= new_flow;
            capacity[current][prev] += new_flow;
            current = prev;
        }
    }

    return max_flow;
}

int main() {
    int n, m; // Number of vertices and edges
    fin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, cap;
        fin >> u >> v >> cap;
        graph[u].push_back(v);
        graph[v].push_back(u);
        capacity[u][v] = cap;
    }

    int source = 1; // Source vertex
    int sink = n; // Sink vertex

    // cout << "Maximum Flow: " << edmondsKarp(source, sink) << endl;
    fout << edmondsKarp(source, sink);
    return 0;
}