//  https://www.infoarena.ro/problema/maxflow
/*
    Flux maxim
        O retea de transport este un graf orientat in care fiecare muchie are asociata o capacitate si o anumita cantitate de flux. Fluxul primit de fiecare muchie trebuie sa fie mai mic 
     sau egal decat capacitatea acesteia. De asemenea, pentru fiecare nod, fluxul care intra in nod trebuie sa fie egal cu cantitatea de flux care iese din nod. Cu alte cuvinte, suma fluxurilor asociate muchiilor care intra intr-un nod trebuie sa fie egala cu suma fluxurilor asociate muchiilor care ies din nod, exceptie facand nodurile speciale S si D, denumite sursa, respectiv, destinatie. Din nodul sursa poate doar iesi flux, in timp ce in nodul destinatie poate doar intra flux. Valoarea fluxului unei astfel retele este egal cu suma fluxului care iese din sursa sau cu suma fluxului care intra in destinatie (cele doua fluxuri sunt egale).

    Cerinta 
        Dandu-se o retea de transport, in care initial fluxul pe fiecare muchie este 0, sa se calculeze fluxul maxim care poate fi trimis prin aceasta retea.

    Date de intrare
        Fisierul de intrare maxflow.in va contine pe prima linie 2 numere, N si M, reprezentand numarul de noduri si numarul de muchii din retea. Pe fiecare din urmatoarele M linii, se vor 
    afla cate 3 numere naturale, x, y si z, cu semnificatia ca exista o muchie care porneste de la nodul x, ajunge in nodul y si are capacitatea z.

    Date de ieşire
        In fisierul de iesire maxflow.out se va afla un singur numar F, reprezentand fluxul maxim ce poate fi trimis prin retea.  
*/

#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std; 

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

int nrNoduri, nrMuchii;

vector<vector<int>> adiacenta, capacitateReziduala;
vector<int> parinte; 

bool BFS(int nodInceput, int nodSfarsit)
{
    vector <bool> vizitat(nrNoduri + 1, false); 
    parinte[nodInceput] = -1; 
    vizitat[nodInceput] = true; 

    queue <int> q; 
    q.push(nodInceput); 

    while (!q.empty())
    {
        int nodCurent = q.front(); 
        q.pop(); 

        for (int nodVecin : adiacenta[nodCurent])
        {
            if (!vizitat[nodVecin] && capacitateReziduala[nodCurent][nodVecin])
            {
                parinte[nodVecin] = nodCurent; 

                if (nodVecin == nodSfarsit)
                    return true; 

                vizitat[nodVecin] = true;
                q.push(nodVecin); 
            }
        }
    }
    return false;
}


int cautaFluxMax(int nodInceput, int nodSfarsit)
{
    long fluxMax = 0; 

    while (BFS(nodInceput, nodSfarsit))
    {
        int fluxCrt = INT_MAX; 
        for (int nodCrt = nodSfarsit; nodCrt != nodInceput; nodCrt = parinte[nodCrt])
            fluxCrt = min(fluxCrt, capacitateReziduala[parinte[nodCrt]][nodCrt]); 

        for (int nodCrt = nodSfarsit; nodCrt != nodInceput; nodCrt = parinte[nodCrt])
        {
            capacitateReziduala[parinte[nodCrt]][nodCrt] -= fluxCrt; 
            capacitateReziduala[nodCrt][parinte[nodCrt]] += fluxCrt; 
        }
        fluxMax += fluxCrt; 
    }
    return fluxMax; 
}

int main()
{
    fin >> nrNoduri >> nrMuchii; 

    int sursa = 1, destinatie = nrNoduri; 

    adiacenta.resize(nrNoduri + 1); 
    parinte.resize(nrNoduri + 1); 
    capacitateReziduala.resize(nrNoduri + 1, vector<int>(nrNoduri + 1));  //initializam grafiul rezidual cu valorile grfului original 

    for (int i = 1; i <= nrMuchii; i++)
    {
        int nodIntrare, nodIesire, capacitate; 
        fin >> nodIntrare >> nodIesire >> capacitate; 

        //initializam graful rezidual cu valorile grafului original 
        capacitateReziduala[nodIntrare][nodIesire] = capacitate;

        adiacenta[nodIntrare].push_back(nodIesire); 
        adiacenta[nodIesire].push_back(nodIntrare); 
    }

    fout << cautaFluxMax(sursa, destinatie) << '\n';
}