#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

// ford-fulkerson or edmonds-karp algorithms for max flow

struct Edge
{
    int to, rev;
    int flow, cap;
    Edge(int to, int rev, int cap) : to(to), rev(rev), flow(0), cap(cap) {}
    Edge(int to, int rev, int flow, int cap) : to(to), rev(rev), flow(flow), cap(cap) {}
    Edge() : to(0), rev(0), flow(0), cap(0) {}
};

void addEdge(vector<vector<Edge>>& graph, int x, int y, int c)
{
    graph[x].emplace_back(y, graph[y].size(), c);
    graph[y].emplace_back(x, graph[x].size() - 1, 0);
}

void bfs(const vector<vector<Edge>>& graph, int source, vector<pair<int, int>>& parent)
{
    vector<int> sinkParents;
    vector<int> queue;
    queue.push_back(source);
    parent[source] = make_pair(-2, -2); // mark as visited

    for (size_t i = 0; i < queue.size(); ++i)
    {
        int node = queue[i];
        for (sizer_t j = 0; j < graph[node].size(); ++j)
        {
            Edge edge = graph[node][j];
            if (parent[edge.to].first == -1 && edge.flow < edge.cap)
            {
                parent[edge.to].first = node;
                parent[edge.to].second = j;
                queue.push_back(edge.to);
            }
        }
    }
}

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

    int n, m;
    fin >> n >> m;

    vector<vector<Edge>> graph(n + 1);
    vector<Edge> sinkParents;

    int source = 1, sink = n;
    for (int i = 0; i < m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;
        addEdge(graph, x, y, c);
        if (y == sink)
            sinkParents.emplace_back(x, -1, 0, c);
    }


    int maxFlow = 0;
    int go = 1;
    while (go)
    {
        go = 0;
        vector<pair<int, int>> parent(n + 1, { -1, -1 });
        bfs(graph, source, parent);
        for (size_t i = 0; i < sinkParents.size(); ++i)
        {
            Edge& p = sinkParents[i];
            int node = p.to;
            int maxAdd = p.cap - p.flow;
            if (parent[node].first > -1)
            {
                go = 1;
            }
            else continue;
            while (parent[node].first > 0)
            {
                int prev = parent[node].first;
                int edgeIndex = parent[node].second;
                Edge edge = graph[prev][edgeIndex];

                maxAdd = min(maxAdd, edge.cap - edge.flow);
                node = prev;
            }

            node = p.to;
            while (parent[node].first > 0)
            {
                int prev = parent[node].first;
                int edgeIndex = parent[node].second;
                Edge& edge = graph[prev][edgeIndex];
                Edge& revEdge = graph[edge.to][edge.rev];

                edge.flow += maxAdd;
                revEdge.flow -= maxAdd;
                node = prev;
            }
            p.flow += maxAdd;
            maxFlow += maxAdd;

            if (p.cap - p.flow == 0)
                sinkParents.erase(sinkParents.begin() + i--);
        }
    }

    fout << maxFlow << endl;

    return 0;
}