#include <bits/stdc++.h>
#include <fstream>

using namespace std;

const int MAXN = 1000;

vector<int> G[MAXN + 1];
int capacity[MAXN + 1][MAXN + 1];
int flow[MAXN + 1][MAXN + 1];
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);
        capacity[x][y] += c; 
    }
    f.close();
}

bool bfs(int source, int sink, vector<int>& parent, vector<bool>& visited) {
    fill(visited.begin(), visited.end(), false);
    fill(parent.begin(), parent.end(), -1);

    queue<int> q;
    q.push(source);
    visited[source] = true;

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

        for (int v : G[u]) {
            if (!visited[v] && capacity[u][v] - flow[u][v] > 0) {
                visited[v] = true;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    return visited[sink];
}

int EdmondsKarp(int source, int sink) {
    int maxFlow = 0;
    vector<int> parent(N + 1);
    vector<bool> visited(N + 1);

    while (bfs(source, sink, parent, visited)) {

        for (int v : G[sink]) {
            if (!visited[v]) continue;
            if (capacity[v][sink] - flow[v][sink] <= 0) continue;

            parent[sink] = v;

            int add = INT_MAX;
            for (int u = sink; u != source; u = parent[u]) {
                int p = parent[u];
                add = min(add, capacity[p][u] - flow[p][u]);
            }

            if (add == 0) continue;

            for (int u = sink; u != source; u = parent[u]) {
                int p = parent[u];
                flow[p][u] += add;
                flow[u][p] -= add;
            }

            maxFlow += add;
        }
    }
    return maxFlow;
}

int main() {
    readInput();

    ofstream g("maxflow.out");
    g << EdmondsKarp(1, N);
    g.close();

    return 0;
}