#include <iostream>
#include <fstream>
#include <limits.h>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

constexpr auto oo = 1000000;

struct Node {
    int height;
    long long excess;
    Node(int h, long long e) : height{ h }, excess{ e } {}
};

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

void Relabel_to_Front(ofstream& fout, int N, int S, int T, vector<unordered_map<int, long long>>& liste_muchii) {
    vector<Node> noduri;
    //pentru fiecare nod, setam inaltimea si excesul de flux egale cu 0
    for (int i = 0; i <= N; i++)
        noduri.push_back(Node(0, 0));
    noduri[S].height = N;

    queue<int> L; //coada cu varfuri active ; de fiecare data, iau un nod si scap de tot excesul de flux
    vector<bool> active(N + 1, false);

    //la partea de initializare, pompam flux din sursa(S) in fiecare varf adiacent
    for (const auto& it : liste_muchii[S]) {
        noduri[S].excess -= it.second;
        noduri[it.first].excess = it.second;
        liste_muchii[it.first][S] = it.second;

        L.push(it.first);
        active[it.first] = true; // fiecare varf vecin cu sursa(S) este activ la inceput
    }

    while (!L.empty()) {
        int u = L.front(); // u - varf activ, din care scap de flux
        L.pop();
        do
        {
            for (auto& muchie : liste_muchii[u]) {
                if (noduri[u].height == noduri[muchie.first].height + 1 && muchie.second != 0)
                {
                    long long pompat = min(noduri[u].excess, muchie.second); //minimul dintre excesul lui u si cat pot trimite pe muchie
                    noduri[u].excess -= pompat;
                    muchie.second -= pompat;
                    noduri[muchie.first].excess += pompat;

                    //daca nu am muchie de l muchie.first -> u, o creez, initial cu capacitate 0
                    if (liste_muchii[muchie.first].find(u) == liste_muchii[muchie.first].end()) {
                        liste_muchii[muchie.first][u] = 0;
                    }
                    liste_muchii[muchie.first][u] += pompat;

                    //daca am pompat excesul din u intr-un varf care nu e activ, il pun in lista(L) si il marchez ca activ
                    if (muchie.first != S && muchie.first != T && active[muchie.first] == false) {
                        active[muchie.first] = true;
                        L.push(muchie.first);
                    }
                }
            }
            //daca mai am exces, trebuie sa inalt varful
            if (noduri[u].excess > 0)
                noduri[u].height++;
        } while (noduri[u].excess > 0);
        //am pompat tot excesul, nodul u nu mai este activ
        active[u] = false;
    }

    fout << noduri[T].excess;
}

int main() {
    int N;
    ifstream fin("maxflow.in");
    ofstream fout("maxflow.out");
    vector<unordered_map<int, long long>> liste_muchii;

    readGraph(fin, N, liste_muchii);
    Relabel_to_Front(fout, N, 1, N, liste_muchii);
}