#include <fstream>
#include <queue>
#include <cmath>

#define N 1005
using namespace std;

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

int cap[N][N], flux[N][N], viz[N], tata[N];
vector <int> l[N]; /// lista de muchii
vector <int> li[N]; /// lista de muchii intoarcere
int n, m;
queue<int> c;
int S, T;
int sol_flux;

void Citire()
{
    fin >> n >> m; /// noduri si muchii
    for(int i = 0; i < m; i++)
    {
        int nod1, nod2, c;
        fin >> nod1 >> nod2 >> c;
        l[nod1].push_back(nod2);
        li[nod2].push_back(nod1);
        /// matricea cap tine capacitatea maxima a muchiei nod1-nod2
        cap[nod1][nod2] = c;
        /// matricea flux reprezinta fluxul care trece prin muchia nod1-nod2
        /// care initial e 0
        flux[nod1][nod2] = 0;

    }

    S = 1;
    T = n;
    /*for(int i = 0; i < m; i++)
       for(auto vecin : l[i])
       {
           fout << i <<" "<< vecin <<"\n";
       }
    */

}

int Constr_Lant_Nesat_BF()
{
    int vecin;
    for(int i=0; i<=n; i++)
    {
        tata[i] = 0;
        viz[i] = 0;
    }

    while(c.empty() == 0)
         c.pop();

    c.push(S);
    viz[S] = 1;
    int nod;
    while(c.empty() == 0)
    {

        nod = c.front();
        c.pop();
        for(auto vecin : l[nod])
            if(viz[vecin] == 0 && cap[nod][vecin] > flux[nod][vecin])
        {
            c.push(vecin);
            viz[vecin] = 1;
            tata[vecin] = nod;
            if(vecin == T)
                return 1;
        }
        /// muchia de intoarcere
        for(auto vecin : li[nod])
            if(viz[vecin] == 0 && flux[vecin][nod] > 0)
            {
                c.push(vecin);
                viz[vecin] = 1;
                tata[vecin] = -nod;
                if(vecin == T)
                    return 1;
            }
    }

    return 0;
}

void Reviz_Flux_Lant()
{
    /// plecam in sens invers, de la T -> S

    for(auto vecin : li[T])
        if(flux[vecin][T] != cap[vecin][T] && viz[vecin]==1)
    {

        tata[T] = vecin;
        int flux_min = N*N;
        int nod = T;
        while(nod != S) /// cat timp nodul actual nu e nodul de unde am inceput
        {
            int parent = tata[nod];
            if(parent > 0)
                 {
                     int dif = cap[parent][nod] - flux[parent][nod];
                     flux_min = min(flux_min, dif);
                 }
            else
            {
                flux_min = min(flux_min, flux[nod][-parent]);
            }
            nod = parent;
            if(nod < 0)
                nod = (-1) * nod;
        }

        nod = T;
        while(nod != S)
        {
            int parent = tata[nod];
            if(parent > 0)
                    flux[parent][nod] = flux[parent][nod] + flux_min;

            else
                flux[nod][-parent] = flux[nod][-parent] - flux_min;

            nod = parent;
            if(nod < 0)
                nod = (-1) * nod;

        }

        sol_flux = sol_flux + flux_min;
    }

}

void Implementare()
{
    while(Constr_Lant_Nesat_BF())
        {
          Reviz_Flux_Lant();
        }

    fout << sol_flux;
}

int main()
{
    Citire();
    Implementare();
   /* Reviz_Flux_Lant();
    fout << Constr_Lant_Nesat_BF() <<"\n";
    fout << sol_flux;*/
    return 0;
}