//Zaharia Diana Cristiana

/*Explicatie problema, idee + metoda de rezolvare :

 Push Relabel Algorithm
--gandim problema ca niste tevi cu o sursa de apa(sursa) si o gaura pe unde curge(destinatie)

--matrice a grafului initializata global pt graf rezidual (muchii rez = 0)
--nodul 1 este nodul sursa,iar nodul N este nodul destinatie. (cerinta)

avem nevoie de bfs pentru a afla drumul catre destinatie pornind de la sursa :
( reinitializam q, viz, vect de tati(t) pentru fiecare parcurgere BFS(drum) )

1.verificam in vecinii nevizitati si cu val capacitatii >0 ( atunci putem trimite flux)
2.salvam la fiecare pas tatal nodului pentru a putea reface drumul
la fiecare pas construim arborele BFS (fara destinatie)
Daca am ajuns la destinatie (nodul destinatie este vizitat), am putut gasi drum, altfel nu am gasit drum.

Algoritmul propriuzis de flux :
cat timp mai putem construi drum:{
1. reconstituim drumul prin vectorul de tati => dam reverse pt a fi in ordinea buna
2. gasim capacitatea minima si o adaugam la flux
3. scad capacitatea minima din muchiile drumului
4. adun capacitatea minima la muchiile cu directie opusa -> eficient, folosim conceptul de "execes flux"
}
*/


#include <bits/stdc++.h>
using namespace std;

int N, M, x, y, cap, fluxmax, gr[1001][1001], t[1001];
bool viz[1001];
queue <int> q;

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

int bfs(){

 while (q.empty() == false)
     q.pop();

 for (int i=0; i <= N; i++){

        t[i] = 0;
        viz[i] = false;

    }

 q.push(1);
 viz[1] = 1;

 while(q.empty() == false){

        auto nd = q.front();
        q.pop();

        if (nd == N)
         return true;

        for (int i=1; i <= N; i++)
            if (viz[i] == false && gr[nd][i] > 0){
                q.push(i);
                t[i] = nd;
                viz[i] = true;
            }
    }

    return false;
}


int fluxmaxim(){

    while (bfs()){
        for (int i=1; i < N; i++){
            if (gr[i][N] > 0 && viz[i] == true){
                int frz = i;

                vector <int> drm;
                drm.push_back(N);
                drm.push_back(frz);

                int nd = t[frz];

                if (nd == 1)
                    drm.push_back(nd);

                else{

                    while (nd != 1){

                        drm.push_back(nd);
                        nd = t[nd];

                    }

                    drm.push_back(1);
                }

                reverse(drm.begin(), drm.end());

                int capmin = 1000000;

                for(long long unsigned int i=0; i < drm.size()-1; i++)
                    capmin = min(capmin, gr[drm[i]][drm[i+1]]);

                fluxmax = fluxmax + capmin;


                for(long long unsigned int i=0; i < drm.size()-1; i++){

                    gr[drm[i]][drm[i+1]] = gr[drm[i]][drm[i+1]] - capmin;
                    gr[drm[i+1]][drm[i]] = gr[drm[i+1]][drm[i]] + capmin;

                }


            }

        }

    }

    return fluxmax;
}


int main(){

     f >> N >> M;
    // cin >> N >> M;

    for(int i=0; i < M; i++)
    {
        f >> x >> y >> cap;
        //cin >> x >>y >> cap;
        gr[x][y] = cap;
    }

    g << fluxmaxim();
   // cout << fluxmaxim();

    return 0;

}