// Pompare Preflux.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

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

using namespace std;

const int oo = 1e9;
const int MAX_N = 1000 + 1;
const int MAX_M = 5000 + 1;

ifstream fin{ "maxflow.in" };
ofstream fout{ "maxflow.out" };

int N, M;
vector<vector<int>> adj(MAX_N, vector<int>());

vector<vector<int>> capacity(MAX_N, vector<int>(MAX_N));
vector<vector<int>> flow(MAX_N, vector<int>(MAX_N));

const int inf = 1000000000;

vector<int> height, excess, seen;
queue<int> excess_vertices;

void push(int u, int v)
{
    int d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
    if (excess[v])
        excess_vertices.push(v);
}

void relabel(int u)
{
    int d = inf;
    for (int i = 0; i < N; i++) {
        if (capacity[u][i] - flow[u][i] > 0)
            d = min(d, height[i]);
    }
    if (d < inf)
        height[u] = d + 1;
}

void discharge(int u)
{
    while (excess[u] > 0) {
        if (seen[u] < N) {
            int v = seen[u];
            if (capacity[u][v] - flow[u][v] > 0 && height[u] > height[v])
                push(u, v);
            else
                seen[u]++;
        }
        else {
            relabel(u);
            seen[u] = 0;
        }
    }
}

int max_flow(int s, int t)
{
    height.assign(N, 0);
    height[s] = N;
    flow.assign(N, vector<int>(N, 0));
    excess.assign(N, 0);
    excess[s] = inf;
    for (int i = 0; i < N; i++) {
        if (i != s)
            push(s, i);
    }
    seen.assign(N, 0);

    while (!excess_vertices.empty()) {
        int u = excess_vertices.front();
        excess_vertices.pop();
        if (u != s && u != t)
            discharge(u);
    }

    return excess[t];
}




int main()
{
    fin >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        int u, v, c;
        fin >> u >> v >> c;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);

        capacity[u][v] = c;
        capacity[v][u] = 0;
    }

    int s = 0;
    int t = N - 1;

    fout << max_flow(s, t);
}