/**

Definim o retea de transport ca fiind un graf orientat cu un nod sursa si unul destinatie si cu anumite
capacitati. Scopul nostru este sa transprotam cat mai multe unitati de la nodul sursa la cel destinatie.

Aceasta este problema fluxului maxim intr-un graf orientat.

Pentru a rezolva acesta problema trebuie sa vedem cum sa transportam o cantitate cat mai mare. Sa presupunem
ca avem o catitate anume deja transportata si stim exact cum a fost transportata - adica ce capacitate pe
fiecare muchie.

   3--o--3
   /   5 \   2
  S--o----o-----D
   1  \4       / 3
       o------o
           2

Avem reteaua de transport de mai sus. Sa presupunem ca transportam o unitate de la sursa la destinatie. O
sa avem atunci capacitatile urmatoare:

   3--o--3
   /   4 \   1
  S--o----o-----D
   0  \4       / 3
       o------o
           2

Desi avem aceste capacitati nu este neaparat sa transportam ce am stabilit mai sus asa cap putem adauga
capaciati pe graful transpus. Cu alte cuvinte vom tine un graf rezidual ( asa se cheama ) in care vom adauga
ce am eliminat din celalat graf. Acest lucru se poate face si cu un singur graf care va avea capacitatile
initiale doar intr-un sens si se vor adauga capacitati pe muchia in sens opus:

capacity[last[now]][now] -= Cmin[*neighbour];
capacity[now][last[now]] += Cmin[*neighbour];

   3->o->3                     3--o--3
   /   4 \  1                  /   1 \   1
  S->o--->o---->D             S<-o<---o<----D
   0  \4       /3              1  \0       / 0
       o----->o                    o------o
           2                          0
   graf initial                graf rezidual

De aici putem contura o solutie. Vom trimite flux la fiecare pas pe cel mai scurt drum de la sursa spre
destinatie. DF-ul va merge pe un drum doar daca se poate ( adica capacitatea e pozitiva ). Se poate
demonstra ca fiecare arc critic va aparea in arborele DF cu cel putin un pas mai jos. De aici o sa avem
maxim M arce critice care vor aparea la maxim N distante diferite. Complexitatea va fi de Os(N*M*(N+M)).
Aceasta complexitate este cu mult supraestimata.

O optimizare foarte utila este ca la un anumit pas sa trimitem flux prim mai multe drumuri. Vom construi
arborele DF si vom trimite flux prin toate nodurile legate la destinatie. Trebuie sa avem grija sa modificam
capacitatile inainte sa trecem la urmaturul drum. Complexitatea va ramane aceeasi , insa viteza va creste
substantial deoarece vom construi mai multe drumuri la fiecare pas.

*/

#include <fstream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

const int Nmax = 1010;
const int Mmax = 5010;

ifstream F("maxflow.in");
ofstream G("maxflow.out");

#define IT(type) vector<type>::iterator

int N,M,total_flow;
vector<int> V[Nmax];
vector<int> neighbours;

int capacity[Nmax][Nmax];
int last[Nmax],Cmin[Nmax];

int find_paths(int source,int target)
{
    queue<int> Q;
    memset(last,0,sizeof(last));

    last[source] = -1;
    Q.push( source );

    while ( Q.size() )
    {
        int node = Q.front();
        Q.pop();

        for (IT(int) where=V[node].begin();where!=V[node].end();++where)
            if ( capacity[node][*where] > 0 && last[*where] == 0 )
            {
                last[*where] = node;
                Q.push( *where );
            }
    }

    neighbours.clear();

    for (IT(int) node=V[target].begin();node!=V[target].end();++node)
        if ( last[ *node ] != 0 && capacity[*node][target] > 0 )
            neighbours.push_back( *node );

    if ( last[target] == 0 )
        return 0;
    return 1;
}

int main()
{
    F>>N>>M;
    for (int i=1,x,y,c;i<=M;++i)
    {
        F>>x>>y>>c;
        if ( capacity[x][y] == 0 && capacity[y][x] == 0 )
        {
            V[ x ].push_back( y );
            V[ y ].push_back( x );
        }
        capacity[x][y] += c;
    }

    int source = 1;
    int target = N;

    while ( find_paths(source,target) != 0 )
    {
        int debug = 1;
        for (IT(int) neighbour=neighbours.begin();neighbour!=neighbours.end();++neighbour)
        {
            Cmin[*neighbour] = capacity[*neighbour][target];
            for (int now=*neighbour;now!=source;now=last[now])
                Cmin[*neighbour] = min( Cmin[*neighbour] , capacity[last[now]][now] );
            total_flow += Cmin[*neighbour];

            for (int now=*neighbour;now!=source;now=last[now])
            {
                capacity[last[now]][now] -= Cmin[*neighbour];
                capacity[now][last[now]] += Cmin[*neighbour];
            }
            capacity[*neighbour][target] -= Cmin[*neighbour];
        }
    }

    G<<total_flow<<'\n';
}