#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <queue>

constexpr auto oo = INT_MAX;

using namespace std;

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

int N; //number of vertices in the graph
vector<unordered_map<int, int>> RG; //residual graph

void readGraph(int& N) {
    int M;
    fin >> N >> M;
    RG.assign(N+1, unordered_map<int, int>());
    int x, y, w;
    while (M > 0)
    {
        fin >> x >> y >> w;
        RG[x][y] = w;
        M--;
    }
}

void BFS(int S, int T, bool& isReachable, int& currentFlow) {
    isReachable = true;
    vector<bool> isVisited(N+1, false);
    vector<int> flows(N+1, 0); // flows[i] - the flow that comes in the BFS
    vector<int> parents(N+1, -1);
    queue<int> coada;
    
    coada.push(S);
    parents[S] = S;
    isVisited[S] = true;

    //find the path to send the flow using BFS (in parents)
    while (isVisited[T] == false && !coada.empty()){
        int currentVertex = coada.front();
        isVisited[currentVertex] = true;
        coada.pop();
        for (auto it : RG[currentVertex]) {
            if (isVisited[it.first] == false && it.second != 0) {
                flows[it.first] = it.second;
                isVisited[it.first] = true;
                coada.push(it.first);
                parents[it.first] = currentVertex;
            }
        }
    }

    //can't find a path to destination, we stop
    if (isVisited[T] == false)
    {
        isReachable = false;
        return;
    }

    //we calculate the maximum flow we can send via the path
    int maxFlow{ oo }; //the maximum amount of flow that we can send in the current BFS search
    int currV{ T };
    while (currV != parents[currV]) {
        maxFlow = min(maxFlow, flows[currV]);
        currV = parents[currV];
    }
    currentFlow = maxFlow;

    //we update the residual grapg(RG)
    int u{ parents[T] }, v{ T };
    while (u != v) {
        //
        RG[u][v] -= maxFlow;
        if (RG[u][v] == 0)
            RG[u].erase(v);
        if (RG[v].find(u) == RG[v].end())
            RG[v][u] = 0;
        RG[v][u] += maxFlow;
        //
        v = u;
        u = parents[u];
    }
}

void EdmondsKarp(int N, int S, int T) {
    int totalFlow{ 0 };
    bool reachable{ false };
    while (true) {
        int flow{ 0 };
        BFS(S, T, reachable, flow);
        if (reachable == false)
            break;
        totalFlow += flow;
    }
    fout << totalFlow; //the maximum flow it can be sent in the hole graph
}

int main()
{
    readGraph(N);
    EdmondsKarp(N, 1, N);
}