/**
Implementarea de mai jos a algoritmului Ford Fulkerson se numește algoritm Edmonds-Karp .
Ideea lui Edmonds-Karp este de a folosi BFS în implementarea Ford Fulkerson,
deoarece BFS alege întotdeauna o cale cu un număr minim de muchii.

Algoritmul Edmonds–Karp pentru determinarea fluxului maxim
Vom folosi BFS cu optimizarile :
    - vom parcurge doar pana inainte de destinatie, a
    dica vom merge pana in nodurile care au
      muchie cu N, dar nu si in N inclusiv
    - dupa ce am terminat de parcurs cu BFS si de actualizat graful rezidual  corespunzator,
      pentru fiecare nod X care are muchie cu N, vom actualiza capacitatile de pe drumul (1 - X)
*/
#include <bits/stdc++.h>

using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");

vector<vector<int>> list_ad;
vector<vector<int>> grafR;
vector<int> tata;

int flow_after_BFS()
{
    int n = list_ad.size() - 1;
    vector<bool> viz(n + 1, false);
    queue<int> q;

    ///punem in coada varful de start
    q.push(1);
    viz[1] = true;

    while (!q.empty())
    {
        int current = q.front();
        q.pop();
        ///mergem prin vecinii varfului scos din coada
        for (auto adiacent: list_ad[current]) {
            ///daca nu a mai fost vizitata si daca are capacitatea de flux si daca nu e varful destinatie il puntem in stiva
            if (!viz[adiacent] && grafR[current][adiacent] > 0 && adiacent != n)
            {
                viz[adiacent] = true;
                q.push(adiacent);
                tata[adiacent] = current;
            }
        }
    }

    int max_flow_possible = 0;
    ///daca varfurile vecine destinatiei au fost vizitate in timpul bfs ului
    for (auto adiacent: list_ad[n])
    {
        if (!viz[adiacent]) continue;

        int iP = grafR[adiacent][n];
        int current = adiacent;
        ///aflam fluxul minim care poate fi transportat
        while (current != 1) {
            iP = min(iP, grafR[tata[current]][current]);
            current = tata[current];
        }

        ///updatam graful rezidual , mai intai muchia vecina cu nodul destinatie dupa care ,
        ///folosing vectorul de tati , restul nodurilor pana la sursa
        grafR[adiacent][n] -= iP;
        grafR[n][adiacent] += iP;

        current = adiacent;
        while (current != 1) {
            grafR[tata[current]][current] -= iP;
            grafR[current][tata[current]] += iP;
            current = tata[current];
        }

        ///adaugam in rezultat fluxul minim
        max_flow_possible += iP;
    }

    return max_flow_possible;
}

int get_max_flow()
{
    ///initializam vec de tati si ultimul nod
    int n = list_ad.size() - 1;
    tata.resize(n + 1, -1);

    int total_max_flow = 0;

    ///luam primul augmenting path
    int path_flow = flow_after_BFS();

    ///cat timp avem augmenting path
    while (path_flow)
    {
        ///adaugam la rezultat ce a returnat functia
        total_max_flow += path_flow;

        ///apelam iar functia pentru aflarea unui augmenting path
        path_flow = flow_after_BFS();
    }

    return total_max_flow;
}

int main() {

    int n, m;
    f >> n >> m;

    list_ad.resize(n + 1);
    grafR.resize(n + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; ++i)
    {
        ///citim datele si punem in lista de adiacenta si in graful rezidual
        int node1, node2, edge_capacity;
        f >> node1 >> node2 >> edge_capacity;
        list_ad[node1].push_back(node2);
        list_ad[node2].push_back(node1);
        grafR[node1][node2] += edge_capacity;
    }

    ///apelam functia pentru max_flow
    g << get_max_flow();

    return 0;
}