#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1000 + 1;
const int Mmax = 5000 + 1;
const int NIL = -1;

struct Edge
{
    int nod;

    int capacity;
    int flow;

    int urm;
};

Edge G[2 * Mmax];
int head[Nmax];

int countHeights[2 * Nmax];
int height[Nmax];
int excess[Nmax];
bool active[Nmax];
int pointer[Nmax];

queue<int> Q;

int N, M;
int countEdges;

void addEdge(int x, int y, int c1, int c2)
{
    G[countEdges] = {y, c1, 0, head[x]};
    head[x] = countEdges++;

    G[countEdges] = {x, c2, 0, head[y]};
    head[y] = countEdges++;
}

void enqueue(int u)
{
    if (!active[u] && excess[u] > 0)
    {
        active[u] = true;
        Q.push(u);
    }
}

void gap(int k)
{
    for (int i = 1; i <= N; ++i)
    {
        if (height[i] >= k)
        {
            countHeights[ height[i] ]--;
            height[i] = max(height[i], N + 1);
            countHeights[ height[i] ]++;

            enqueue(i);
        }
    }
}

void push(int u, int p)
{
    int v = G[p].nod;
    int delta = min(excess[u], G[p].capacity - G[p].flow);

    G[p].flow += delta;
    G[p ^ 1].flow -= delta;

    excess[u] -= delta;
    excess[v] += delta;

    enqueue(v);
}

void relabel(int u)
{
    countHeights[ height[u] ]--;
    height[u] = 2 * N;

    for (int p = head[u]; p != NIL; p = G[p].urm)
    {
        int v = G[p].nod;

        if (G[p].capacity > G[p].flow)
            height[u] = min(height[u], height[v] + 1);
    }

    countHeights[ height[u] ]++;
    enqueue(u);
}

void discharge(int u)
{
    bool doneGap = false;

    while (excess[u] > 0)
    {
        if (doneGap == false && countHeights[ height[u] ] == 1)
        {
            gap(height[u]);
            doneGap = true;
            pointer[u] = NIL;
        }

        if (pointer[u] != NIL)
        {
            int p = pointer[u];
            int v = G[p].nod;

            if (height[u] >= height[v] + 1 && G[p].capacity > G[p].flow)
                push(u, p);

            pointer[u] = G[ pointer[u] ].urm;
        }
        else
        {
            relabel(u);
            pointer[u] = head[u];
        }
    }
}

void initPreflow(int S, int T)
{
    for (int i = 0; i <= 2 * N; ++i)
        countHeights[i] = 0;

    for (int i = 1; i <= N; ++i)
    {
        active[i] = false;
        pointer[i] = head[i];
        height[i] = 0;
        excess[i] = 0;
    }

    height[S] = N;
    countHeights[N] = 1;
    countHeights[0] = N - 1;

    active[S] = active[T] = true;

    for (int p = head[S]; p != NIL; p = G[p].urm)
    {
        excess[S] += G[p].capacity;
        push(S, p);
    }
}

int push_relabel(int S, int T)
{
    initPreflow(S, T);

    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        active[u] = false;
        discharge(u);
    }

    int flow = 0;

    for (int p = head[S]; p != NIL; p = G[p].urm)
        flow += G[p].flow;

    return flow;
}

int main()
{
    ifstream in("maxflow.in");
    ofstream out("maxflow.out");

    in >> N >> M;

    for (int i = 1; i <= N; ++i)
        head[i] = NIL;

    for (int i = 0; i < M; ++i)
    {
        int a, b, c;
        in >> a >> b >> c;

        addEdge(a, b, c, 0);
    }

    out << push_relabel(1, N);

    return 0;
}