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

const int maxN = 1001;

bool BFS(int src, int N, vector<int> adjList[],
         int flow[][maxN], int capacity[][maxN], int parent[]);

int main()
{
    int N, M, i, j, x, y ,c;
    ifstream f("maxflow.in");
    f >> N >> M;
    vector<int> adjList[N + 1];
    int flow[N + 1][maxN], capacity[N + 1][maxN], parent[N + 1];

    for (i = 1; i <= N; i++)
    {
        fill(flow[i] + 1, flow[i] + N + 1, 0);
        fill(capacity[i] + 1, capacity[i] + N + 1, 0);
    }

    for (i = 1; i <= M; i++)
    {
        f >> x >> y >> c;
        adjList[x].push_back(y);
        adjList[y].push_back(x);
        capacity[x][y] = c;
    }

    int minFlow = INT_MAX, result = 0;
    while (BFS(1, N, adjList, flow, capacity, parent))
    {
        for (i = N; parent[i] != -1; i = parent[i])
            minFlow = min(minFlow, capacity[parent[i]][i] - flow[parent[i]][i]);

        for (i = N; parent[i] != -1; i = parent[i])
        {
            flow[parent[i]][i] += minFlow;
            flow[i][parent[i]] -= minFlow;
        }

        result += minFlow;
    }

    ofstream g("maxflow.out");
    g << result;
    g.close();

    return 0;
}

bool BFS(int src, int N, vector<int> adjList[],
         int flow[][maxN], int capacity[][maxN], int parent[])
{
    bool visited[N + 1];
    fill(visited + 1, visited + N + 1, false);

    queue<int> q;
    q.push(src);
    visited[src] = true;
    parent[src] = -1;

    int x, i;
    while (!q.empty())
    {
        x = q.front();
        q.pop();
        for (i = 0; i < adjList[x].size(); i++)
        {
            int neighbor = adjList[x][i];
            if (capacity[x][neighbor] != flow[x][neighbor] && !visited[neighbor])
            {
                visited[neighbor] = true;
                q.push(neighbor);
                parent[neighbor] = x;
                if (neighbor == N)
                    return true;
            }
        }
    }

    return false;
}