// PUSH RELABEL WITH MAXIMUM HEIGHT

#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#include <fstream>
#define VMAX 1000

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int V, E, x, y;
int flow[VMAX][VMAX], capacity[VMAX][VMAX];
int height[VMAX], excess[VMAX];

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;
}

void relabel(int u)
{
    int mn = INT_MAX;

    for (int i = 0; i < V; ++i)
        if (capacity[u][i] - flow[u][i] > 0) // positive residual capacity => is in G_f
        mn = min(mn, height[i]);

    if (mn < INT_MAX)
        height[u] = mn + 1;
}

void init()
{
    height[0] = V;
    excess[0] = INT_MAX;

    for (int u = 1; u < V; ++u)
        push(0, u);
}

vector <int> find_max_height_vertices()
{
    vector <int> max_height;

    for (int i = 1; i < V - 1; ++i)
    {
        if (excess[i] > 0)
        {
            if (!max_height.empty() && height[i] > height[max_height[0]])
                max_height.clear();
            if (max_height.empty() || height[i] == height[max_height[0]])
                max_height.push_back(i);
        }
    }

    return max_height;
}

int max_flow()
{
    vector <int> current = find_max_height_vertices();

    while (!current.empty())
    {
        for (int i:current)
        {
            bool pushed = false;
            for (int j = 0; j < V && excess[i]; ++j) {
                if (capacity[i][j] - flow[i][j] > 0 && height[i] == height[j] + 1)
                {push(i, j); pushed = true;}
            }
            if (!pushed)
            {
                relabel(i);
                break;
            }
        }
        current = find_max_height_vertices();
    }

    int maximum = 0;
    for (int i = 0; i < V; ++i)
        maximum += flow[i][V - 1];
    return maximum;
}

int main()
{
    fin >> V >> E;

    while (E--)
        fin >> x >> y >> capacity[x - 1][y - 1];

    init();

    fout << max_flow();

    fin.close();
    fout.close();
    return 0;
}