#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream cin("maxflow.in");
ofstream cout("maxflow.out");

#define MAXN 1005
#define INF INT_MAX

// Edge structure for the graph and reverse edge
struct Edge {
    int to, rev;
    int capacity, flow;
};

vector<Edge> graph[MAXN + 1]; // Adjacency list (1-based index)
int level[MAXN + 1];          // Level of each node in BFS
int ptr[MAXN + 1];            // Pointer for DFS in each node

// Function to add an edge to the graph
void addEdge(int u, int v, int cap) {
    graph[u].push_back({v, graph[v].size(), cap, 0}); // Forward edge
    graph[v].push_back({u, graph[u].size() - 1, 0, 0}); // Reverse edge (initial flow 0)
}

// BFS to construct the level graph
bool bfs(int source, int sink) {
    memset(level, -1, sizeof(level)); // Initialize level to -1 (not visited)
    level[source] = 0;
    queue<int> q;
    q.push(source);

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

        for (auto& edge : graph[u]) {
            if (level[edge.to] == -1 && edge.flow < edge.capacity) {
                level[edge.to] = level[u] + 1;
                q.push(edge.to);
                if (edge.to == sink) return true; // If we reached the sink, path is found
            }
        }
    }

    return false; // No augmenting path found
}

// DFS to push flow along the augmenting path
int dfs(int u, int sink, int flow) {
    if (u == sink) return flow; // If we've reached the sink, return the flow to push

    for (; ptr[u] < graph[u].size(); ptr[u]++) {
        Edge &edge = graph[u][ptr[u]];

        // If there's available flow and level condition is satisfied
        if (level[edge.to] == level[u] + 1 && edge.flow < edge.capacity) {
            int availableFlow = edge.capacity - edge.flow;
            int currFlow = min(flow, availableFlow);

            int pushed = dfs(edge.to, sink, currFlow); // Recursively push flow
            if (pushed > 0) {
                edge.flow += pushed; // Update forward edge flow
                graph[edge.to][edge.rev].flow -= pushed; // Update reverse edge flow
                return pushed;
            }
        }
    }

    return 0; // No more flow could be pushed
}

// Dinic's Algorithm to find the maximum flow
int dinic(int source, int sink, int n) {
    int maxFlow = 0;

    while (bfs(source, sink)) { // Repeat until no augmenting path is found
        memset(ptr, 0, sizeof(ptr)); // Reset DFS pointer
        int flow;
        while ((flow = dfs(source, sink, INF)) > 0) { // Push as much flow as possible
            maxFlow += flow;
        }
    }

    return maxFlow;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, cap;
        cin >> u >> v >> cap;
        addEdge(u, v, cap);
    }

    int source = 1, sink = n;
    int maxFlow = dinic(source, sink, n);
    cout << maxFlow;

    return 0;
}