#include <bits/stdc++.h>
using namespace std;
ifstream f("maxflow.in");
ofstream o("maxflow.out");
vector<vector<int>> la;
vector<vector<int>> grafR;
vector<int> tati;
int flow_after_BFS() {

    int n = la.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: la[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);
                tati[adiacent] = current;
            }
        }
    }

    int max_flow_possible = 0;
    //daca varfurile vecine destinatiei au fost vizitate in timpul bfs ului
    for (auto adiacent: la[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[tati[current]][current]);
            current = tati[current];
        }
        //updatam graful rezidual , mai intai muchia vecina cu nodul destinatie dupa care ,
        // folosing vectorul de tati , restul nodurilor pana la sursa

       // cout<<"iP = "<<iP<<"\n";
        //cout<<"adiacent = "<<adiacent<<", "<<"n= "<<n<<" ,grafR[adiacent][n]= "<<grafR[adiacent][n]<<"\n";
        grafR[adiacent][n] -= iP;
        //cout<<"adiacent = "<<adiacent<<", "<<"n= "<<n<<" ,grafR[adiacent][n]= "<<grafR[adiacent][n]<<"\n";
        //cout<<"adiacent = "<<adiacent<<", "<<"n= "<<n<<" ,grafR[n][adiacent]= "<<grafR[n][adiacent]<<"\n";
        grafR[n][adiacent] += iP;
        //cout<<"adiacent = "<<adiacent<<", "<<"n= "<<n<<" ,grafR[n][adiacent]= "<<grafR[n][adiacent]<<"\n";

        current = adiacent;
        while (current != 1) {
            //cout<<"current = "<<current<<" , n= "<<n<<" , grafR[tati[current]][current] = "<<grafR[tati[current]][current]<<"\n";
            grafR[tati[current]][current] -= iP;
            //cout<<"current = "<<current<<" , n= "<<n<<" , grafR[tati[current]][current] = "<<grafR[tati[current]][current]<<"\n";
            //cout<<"current = "<<current<<" , n= "<<n<<" , grafR[current][tati[current]] = "<<grafR[current][tati[current]]<<"\n";
            grafR[current][tati[current]] += iP;
            //cout<<"current = "<<current<<" , n= "<<n<<" , grafR[current][tati[current]] = "<<grafR[current][tati[current]]<<"\n";
            current = tati[current];
        }
        //adaugam in rezultat fluxul minim
        max_flow_possible += iP;
    }

    return max_flow_possible;
}

int get_max_flow() {
    int n = la.size() - 1;
    //initializam vec de tati si ultimul nod
    tati.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;

    la.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;
        la[node1].push_back(node2);
        la[node2].push_back(node1);
        grafR[node1][node2] += edge_capacity;
    }
    //apelam functia pentru max_flow
    o << get_max_flow();

    return 0;
}


/*
Algoritmul Edmonds–Karp  determinarea fluxului maxim
O(N * M * M);
Vom folosi BFS cu optimizarile :
    - vom parcurge doar pana inainte de destinatie, adica 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)
*/