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

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

const int MAX_N = 1001;
const int NONE = -1;

std::vector<int> neigh; // From those, dest is 1 step away
int graph[MAX_N][MAX_N];
int parent[MAX_N];
int n, m;
int maxflow;

void build_graph()
{
    int u, v, c;

    f >> n >> m;

    for (int i = 0; i < m; i ++) {
        f >> u >> v >> c;

        graph[u][v] = c;
    }
}

void bfs(int source)
{
    std::queue<int> q;

    q.push(source);

    for (int i = 1; i <= n; i ++) {
        parent[i] = NONE;
    }
    neigh.clear();

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

        q.pop();

        for (int v = 1; v <= n; v ++) {
            if (graph[u][v] && parent[v] == NONE) {
                q.push(v);
                parent[v] = u;
            }
        }

        if (graph[u][n]) {
            neigh.push_back(u);
        }
    }
}

int pick_path(int u)
{
    // Compute the maximum flow for a path that goes through the (u, n) edge.
    int maxf = graph[u][n];
    int v = u;

    while (v != 1) {
        maxf = std::min(maxf, graph[parent[v]][v]);
        v = parent[v];
    }

    // Saturate the path.
    graph[u][n] -= maxf;
    graph[n][u] += maxf;

    v = u;
    while (v != 1) {
        graph[parent[v]][v] -= maxf;
        graph[v][parent[v]] += maxf;
        v = parent[v];
    }

    return maxf;
}

void compute_flow()
{
    bfs (1);

    if (neigh.size() == 0) {
        return;
    }

    for (int i = 0; i < (int)neigh.size(); i ++) {
        maxflow += pick_path(neigh[i]);
    }

    compute_flow();
}

int main()
{
    build_graph();
    compute_flow();

    g << maxflow << '\n';

    return 0;
}