#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];

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

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

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

    maxflow = 0;
    dest = n, src = 1;
    while (buildBFSTree(src, dest))
    {
        len = edges[dest].size();
        for (int i = 0; i < len; i++)
        {
            v = edges[dest][i];
            if (vis[v] && flow[v][dest] != cap[v][dest])
                maxflow += pushFlow(v, 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;
    l = 0;
    r = 1;
    q[0] = src, vis[0] = 1;
    father[src] = 0;
    while (l < r)
    {

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

}

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