#include <fstream>
#include <queue>
using namespace std;

const int maxNodes = 1000;
const int maxInt= ~(1 << (sizeof(int) * 8 - 1));

int getMaxFlow(int adjMatrix[][maxNodes], int N);
bool BFS(int src, int target, int parent[], int adjMatrix[][maxNodes],
         queue<int> &leaves, int N);

int main()
{
    int N, M, i;
    ifstream f("maxflow.in");
    f >> N >> M;
    int adjMatrix[N + 1][maxNodes];

    for (i = 1; i <= N; i++)
        fill(adjMatrix[i] + 1, adjMatrix[i] + N + 1, 0);

    int x, y, c;
    for (i = 1; i <= M; i++)
    {
        f >> x >> y >> c;
        adjMatrix[x][y] = c;
    }
    f.close();

    ofstream g("maxflow.out");
    g << getMaxFlow(adjMatrix, N);
    g.close();

    return 0;
}

int getMaxFlow(int adjMatrix[][maxNodes], int N)
{
    int parent[N + 1], x, minFlow, result = 0;
    queue<int> leaves;
    while (BFS(1, N, parent, adjMatrix, leaves, N))
    {
        while (!leaves.empty())
        {
            minFlow = maxInt;
            parent[N] = leaves.front(), leaves.pop();
            x = N;
            while (parent[x] != -1)
            {
                minFlow = min(minFlow, adjMatrix[parent[x]][x]);
                x = parent[x];
            }

            x = N;
            while (parent[x] != -1)
            {
                adjMatrix[parent[x]][x] -= minFlow;
                adjMatrix[x][parent[x]] += minFlow;
                x = parent[x];
            }

            result += minFlow;
        }
    }

    return result;
}

bool BFS(int src, int target, int parent[], int adjMatrix[][maxNodes],
         queue<int> &leaves, int N)
{
    bool visited[N + 1], isLeaf;
    fill(visited + 1, visited + N + 1, false);

    int x, i;
    queue<int> q;

    q.push(src);
    parent[src] = -1;
    visited[src] = true;
    while (!q.empty())
    {
        x = q.front(), q.pop();
        isLeaf = true;
        for (i = 1; i < N; i++)
            if (!visited[i] && adjMatrix[x][i])
            {
                isLeaf = false;
                q.push(i);
                visited[i] = true;
                parent[i] = x;
            }

        // check connection to target
        if (isLeaf && adjMatrix[x][N])
            leaves.push(x);
    }

    return !leaves.empty();
}