#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;
const int NMAX = 1000, INF = 1e9;


vector<int> edges[NMAX + 1];
int cap[NMAX + 1][NMAX + 1], flow[NMAX + 1][NMAX + 1], q[NMAX], father[NMAX + 1];
bool vis[NMAX + 1], connToDest[NMAX + 1];

void reset(int n);
bool buildBFSTree(int src, int dest);
int pushFlow(int node, int dest);

int main()
{
    int n, m, v1, v2, maxflow, dest, src;
    FILE *fin = fopen("maxflow.in", "r");

    fscanf(fin, "%d%d", &n, &m);
    dest = n, src = 1;
    for (int i = 0; i < m; i++)
    {
        fscanf(fin, "%d%d", &v1, &v2);
        fscanf(fin, "%d", &cap[v1][v2]);
        edges[v1].push_back(v2);
        if (v2 == dest)
            connToDest[v1] = 1;
    }
    fclose(fin);

    maxflow = 0;
    while (buildBFSTree(src, dest))
    {
        for (int i = n - 1; i > 0; i--)
            if (connToDest[i] == 1)
                maxflow += pushFlow(i, dest);
        reset(n);
    }

    FILE *fout = fopen("maxflow.out", "w");
    fprintf(fout, "%d", maxflow);
    fclose(fout);
    return 0;
}

void reset(int n)
{
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
}

bool buildBFSTree(int src, int dest)
{
    int node, nextn, i, len, l, r;
    bool ok = 0;
    l = 0;
    r = 1;
    q[0] = src;
    father[src] = 0;
    while (l < r)
    {
        node = q[l++];
        len = edges[node].size();
        for (i = 0; i < len; i++)
        {
            nextn = edges[node][i];
            if (nextn == dest)
            {
                ok = 1;
                continue;
            }
            if (!vis[nextn] && flow[node][nextn] != cap[node][nextn])
            {
                vis[nextn] = 1;
                q[r++] = nextn;
                father[nextn] = node;
            }
        }
    }
    return ok;

}

int pushFlow(int node, int dest)
{
    father[dest] = node;
    int lastNode = dest;
    int maxflow = INF;
    while (node)
    {
        maxflow = min(maxflow, cap[node][lastNode] - flow[node][lastNode]);
        lastNode = node;
        node = father[node];
    }
    node = father[dest], lastNode = dest;
    while (node)
    {
        flow[node][lastNode] += maxflow;
        flow[lastNode][node] -= maxflow;
        lastNode = node;
        node = father[node];
    }
    return maxflow;
}