/*
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.

Restricţii
2 ≤ N ≤ 1 000
1 ≤ M ≤ 5 000
Nodul 1 este nodul sursa, iar nodul N este nodul destinatie.
Pentru fiecare muchie, capacitatea va fi un numar natural in intervalul [1, 110 000].
Nu exista nici o muchie x y astfel incat x sa fie egal cu N sau y sa fie egal cu 1.
Intre oricare doua noduri x si y exista maxim un arc, însă arcele x -> y şi y -> x pot exista simultan.
In practica, retelele de flux contin adesea un numar mare de noduri vecine cu destinatia. Testele folosite la evaluarea vitezei algoritmului de flux de la aceasta problema au aceeasi proprietate.

IN:
4 5
1 2 3
1 3 5
2 4 6
3 4 4
3 2 3

OUT:
8
*/

/// Dinic's algorithm with Capacity Scaling - Solutie de , Complexitate: O(log(C) * m * n)   C - Capacitatea maxima a unei muchii, m - Nr. de muchii, n - Nr. de noduri
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 1005

using namespace std;

map < pair < int, int >, int > h;
vector < int > v[MAX];
int n, prag, nvl[MAX];
bool dead_end[MAX];

void nivelare(int nod);
int dfs(int nod, int minn);

int main()
{
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");
    int m, i, x, y, z, r = 0;

    cin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        v[x].pb(y), h[{x, y}] = z;
        if(h[{y, x}] == 0) v[y].pb(x);
    }

    nivelare(1);
    while(nvl[n] != 0)
    {
        while(prag != 0)
        {
            x = dfs(1, INT_MAX);
            if(x != 0) r += x;
            else
            {
                prag /= 2;
                for(i = 1; i <= n; i++) dead_end[i] = 0;
            }
        }
        nivelare(1);
    }
    cout << r;

    return 0;
}

void nivelare(int nod)
{
    int maxx = 0;

    queue < int > q;
    for(int i = 1; i <= n; i++) nvl[i] = 0, dead_end[i] = 0;

    nvl[nod] = 1, q.push(nod);
    while(q.empty() == 0)
    {
        nod = q.front(), q.pop();
        for(int it:v[nod])
        {
            if(nvl[it] == 0 || nvl[it] == nvl[nod] + 1) maxx = max(maxx, h[{nod, it}]);
            if (nvl[it] == 0 && h[{nod, it}] > 0)
            {
                nvl[it] = nvl[nod] + 1;
                q.push(it);
            }
        }
    }

    prag = (1<<int(log2(maxx)));
}

int dfs(int nod, int minn)
{
    if(nod == n) return minn;

    for(int it:v[nod]) if(nvl[it] == nvl[nod] + 1 && dead_end[it] == 0 && h[{nod, it}] >= prag)
        {
            int x = dfs(it, min(minn, h[{nod, it}]));
            if(x > 0)
            {
                h[{nod, it}] -= x;
                h[{it, nod}] += x;
                return x;
            }
            else dead_end[it] = 1;
        }

    return 0;
}


/// Dinic's algorithm - Solutie de 100 de puncte, Complexitate: O(m * n * n)   m - Nr. de muchii, n - Nr. de noduri
/*
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 1005

using namespace std;

map < pair < int, int >, int > h;
vector < int > v[MAX];
int n, nvl[MAX];
bool dead_end[MAX];

void nivelare(int nod);
int dfs(int nod, int minn);

int main()
{
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");
    int m, i, x, y, z, r = 0;

    cin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        v[x].pb(y), h[{x, y}] = z;
        if(h[{y, x}] == 0) v[y].pb(x);
    }

    nivelare(1);
    while(nvl[n] != 0)
    {
        x = 1;
        while(x != 0)
        {
            x = dfs(1, INT_MAX);
            r += x;
        }
        nivelare(1);
    }
    cout << r;

    return 0;
}

void nivelare(int nod)
{
    queue < int > q;
    for(int i = 1; i <= n; i++) nvl[i] = 0, dead_end[i] = 0;

    nvl[nod] = 1, q.push(nod);
    while(q.empty() == 0)
    {
        nod = q.front(), q.pop();
        for(int it:v[nod]) if(nvl[it] == 0 && h[{nod,it}] > 0)
        {
            nvl[it] = nvl[nod] + 1;
            q.push(it);
        }
    }
}

int dfs(int nod, int minn)
{
    if(nod == n) return minn;

    for(int it:v[nod]) if(nvl[it] == nvl[nod] + 1 && dead_end[it] == 0 && h[{nod, it}] > 0)
    {
        int x = dfs(it, min(minn, h[{nod, it}]));
        if(x > 0)
        {
            h[{nod, it}] -= x;
            h[{it, nod}] += x;
            return x;
        }
        else dead_end[it] = 1;
    }

    return 0;
}
*/

/// Edmonds-Karp algorithm with Capacity Scaling - Solutie de 70 de puncte, Complexitate: O(log(C) * m * n)   C - Capacitatea maxima a unei muchii, m - Nr. de muchii, n - Nr. de noduri
/// Atentie: In practica constanta este mare, si nu are rezultate f. bune
/*
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 1005

using namespace std;

vector < int > v[MAX];
map < pair < int, int >, int > h;
int n, prag, prec[MAX];
bool viz[MAX];

int bfs(int nod);

int main()
{
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");
    int m, i, x, y, z, maxx = 0, r = 0;

    cin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        v[x].pb(y), h[{x, y}] = z, maxx = max(maxx, z);
        if(h[{y, x}] == 0) v[y].pb(x);
    }

    prag = (1<<int(log2(maxx)));
    while(prag != 0)
    {
        for(i = 1; i <= n; i++) viz[i] = 0;
        prec[1] = 0;
        x = bfs(1);

        if(x != 0) r += x;
        else prag /= 2;
    }
    cout << r;

    return 0;
}

int bfs(int nod)
{
    int minn = INT_MAX, i;

    queue < int > q;
    q.push(nod), viz[nod] = 1;
    while(q.empty() == 0)
    {
        nod = q.front(), q.pop();
        for(int it:v[nod]) if(viz[it] == 0 && h[{nod,it}] >= prag)
            {
                prec[it] = nod;
                if(it == n)
                {
                    i = n;
                    while(prec[i] != 0)
                    {
                        minn = min(minn, h[{prec[i], i}]);
                        i = prec[i];
                    }

                    i = n;
                    while(prec[i] != 0)
                    {
                        h[{prec[i], i}] -= minn;
                        h[{i, prec[i]}] += minn;
                        i = prec[i];
                    }

                    return minn;
                }
                else q.push(it), viz[it] = 1;
            }
    }

    return 0;
}
*/

/// Edmonds-Karp algorithm - Solutie de 70 de puncte, Complexitate: O(n * m * m), m - Nr. de muchii, n - Nr. de noduri
/*
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 1005

using namespace std;

vector < int > v[MAX];
map < pair < int, int >, int > h;
int n, prec[MAX];
bool viz[MAX];

int bfs(int nod);

int main()
{
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");
    int m, i, x, y, z, r = 0;

    cin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        v[x].pb(y), h[{x, y}] = z;
        if(h[{y, x}] == 0) v[y].pb(x);
    }

    x = 1;
    while(x != 0)
    {
        for(i = 1; i <= n; i++) viz[i] = 0;
        prec[1] = 0;
        x = bfs(1);
        r += x;
    }
    cout << r;

    return 0;
}

int bfs(int nod)
{
    int minn = INT_MAX, i;

    queue < int > q;
    q.push(nod), viz[nod] = 1;
    while(q.empty() == 0)
    {
        nod = q.front(), q.pop();
        for(int it:v[nod]) if(viz[it] == 0 && h[{nod,it}] > 0)
        {
            prec[it] = nod;
            if(it == n)
            {
                i = n;
                while(prec[i] != 0)
                {
                    minn = min(minn, h[{prec[i], i}]);
                    i = prec[i];
                }

                i = n;
                while(prec[i] != 0)
                {
                    h[{prec[i], i}] -= minn;
                    h[{i, prec[i]}] += minn;
                    i = prec[i];
                }

                return minn;
            }
            else q.push(it), viz[it] = 1;
        }
    }

    return 0;
}
*/

/// Ford-Fulkerson algorithm with Capacity Scaling - Solutie de 70 de puncte, Complexitate: O(log(C) * m * m)   C - Capacitatea maxima a unei muchii, m - Nr. de muchii
/*
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 1005

using namespace std;

map < pair < int, int >, int > h;
vector < int > v[MAX];
int n, prag;
bool viz[MAX];

int dfs(int nod, int minn);

int main()
{
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");
    int m, i, x, y, z, maxx = 0, r = 0;

    cin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        v[x].pb(y), h[{x, y}] = z, maxx = max(maxx, z);
        if(h[{y, x}] == 0) v[y].pb(x);
    }

    prag = (1<<int(log2(maxx)));
    while(prag != 0)
    {
        for(i = 1; i <= n; i++) viz[i] = 0;
        x = dfs(1, INT_MAX);

        if(x != 0) r += x;
        else prag /= 2;
    }
    cout << r;

    return 0;
}

int dfs(int nod, int minn)
{
    viz[nod] = 1;
    if(nod == n) return minn;

    for(int it:v[nod]) if(viz[it] == 0 && h[{nod, it}] >= prag)
        {
            int x = dfs(it, min(minn, h[{nod, it}]));
            if(x > 0)
            {
                h[{nod, it}] -= x;
                h[{it, nod}] += x;
                return x;
            }
        }

    return 0;
}
*/

/// Ford-Fulkerson algorithm - Solutie de 70 de puncte, Complexitate: O(F * m)   F - Fluxul maxim, m - Nr. de muchii
/*
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define MAX 1005

using namespace std;

map < pair < int, int >, int > h;
vector < int > v[MAX];
int n;
bool viz[MAX];

int dfs(int nod, int minn);

int main()
{
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");
    int m, i, x, y, z, r = 0;

    cin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        v[x].pb(y), h[{x, y}] = z;
        if(h[{y, x}] == 0) v[y].pb(x);
    }

    x = 1;
    while(x != 0)
    {
        for(i = 1; i <= n; i++) viz[i] = 0;
        x = dfs(1, INT_MAX);
        r += x;
    }
    cout << r;

    return 0;
}

int dfs(int nod, int minn)
{
    viz[nod] = 1;
    if(nod == n) return minn;

    for(int it:v[nod]) if(viz[it] == 0 && h[{nod, it}] != 0)
    {
        int x = dfs(it, min(minn, h[{nod, it}]));
        if(x > 0)
        {
            h[{nod, it}] -= x;
            h[{it, nod}] += x;
            return x;
        }
    }

    return 0;
}
*/