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

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

const int MAX_N = 1001;

int near[MAX_N], pnear; // From those, dest is 1 step away
int graph[MAX_N][MAX_N];
std::vector<int> neigh[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;

        neigh[u].push_back(v);
        neigh[v].push_back(u);
    }
}

void bfs(int source)
{
    int qu[MAX_N * 2];
    int first, last;

    qu[0] = source;
    first = last = 0;

    memset(parent, 0, (n + 1) * sizeof(int));
    pnear = 0;

    while (first <= last) {
        int u = qu[first++];
        int v;

        if (u == n) {
            continue;
        }

        for (int i = 0; i < (int) neigh[u].size(); i ++) {
            v = neigh[u][i];
            if (graph[u][v] && parent[v] == 0) {
                qu[++last] = v;
                parent[v] = u;
            }
        }

        if (graph[u][n]) {
            near[pnear ++] = 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];
    }

    if (maxf == 0) {
        return 0;
    }

    // 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 (pnear == 0) {
        return;
    }

    for (int i = 0; i < pnear; i ++) {
        maxflow += pick_path(near[i]);
    }

    compute_flow();
}

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

    g << maxflow << '\n';

    return 0;
}