#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

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

int start , stop , flow = 2e9 , minim , n , m , a[1005][1005] , level[1005] , maxflow , x , y , c , cnt[10905] , viz[10005] , floulescu;

int dfs (int nod)
{

    if (nod == n)
        return flow;
        if (cnt[nod] == n)
            return 0;
    for (int i = 1 ; i <= n ; i++)
    {
        if (a[nod][i] > 0)
        {
            cnt[nod]++;
            if (level[i] == level[nod] + 1)
            {
                flow = min (flow , a[nod][i]);
                int minim = dfs (i);
                if (minim > 0)
                {
                    a[nod][i] -= minim;
                    a[i][nod] += minim;
                    return minim;
                }
            }
        }
    }
    return 0;

}

int bfs (int start , int stop)
{
    for (int i = 1 ; i <= n ; i++)
        level[i] = -1;
    level[start] = 0;
    queue < int > coada;
    coada.push (start);
    while (!coada.empty ())
    {
        int nod = coada.front ();
        coada.pop ();
        for (int i = 1 ; i <= n ; i++)
        {
            if (a[nod][i] > 0 && level[i] < 0)
            {
                coada.push (i);
                level[i] = level[nod] + 1;
            }
        }
    }
    if (level[stop] > 0)
        return true;
    return false;
}

int dinic (int start , int stop)
{
    if (start == stop)
        return -1;

    while (bfs (start , stop) == true)
    {
        flow = 2e9;
        for (int i = 1 ; i <= n ; i++)
            cnt[i] = 0;
        while (( floulescu = dfs (start)) != 0)
        {
              maxflow += flow;
              flow = 2e9;
        }
    }
    return maxflow;
}

int main()
{
    f >> n >> m;
    for (int i = 1 ; i <= m ; i++)
    {
        f >> x >> y >> c;
        a[x][y] = c;
    }
    g << dinic (1 , n);

   /* for (int i = 1 ; i <= n ; i++)
        g << level[i] << " ";
        g << '\n' << '\n' << '\n';
        for (int i = 1 ; i <= n ; i++)
        {
            for (int j = 1 ; j <= n ; j++)
                g << a[i][j] << " ";
            g << '\n';;
        }
        flow = 2e9;
    g << dfs (1);*/
    return 0;
}