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

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

typedef struct
{
    int flow;
    int capacitate;
} dual;

typedef struct
{
    int val;
    bool out;

} vecin;

int n,m;
vector<vector<vecin>> lista_adiacenta;
vector<int> tata;
dual matrice[1001][1001];
int rezultat = 0;


void citire()
{
    f >> n >> m;
    lista_adiacenta.reserve(n+1);
    int i;
    for(i=0;i<=n;i++)
    {
        vector<vecin> aux;
        lista_adiacenta.push_back(aux);
    }

    int x,y,z;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        matrice[x][y].capacitate = z;
        matrice[x][y].flow = 0;
        lista_adiacenta[x].push_back({y,true});
        lista_adiacenta[y].push_back({x,false});
    }
}

bool BFS()
{

    //cout << "\n\n\nBFS\n\n\n";
    queue<int> coada;
    tata.clear();
    tata.resize(n+1, 0);
    vector<bool> vizitat;
    vizitat.resize(n+1, false);

    coada.push(1);
    vizitat[1] = true;

    int curent;
    int destinatie;
    int rezidual;

    while(!coada.empty())
    {
        curent = coada.front();
        coada.pop();

        for(auto &it : lista_adiacenta[curent])
        {
            destinatie = it.val;
            if(!vizitat[destinatie])
            {
                if(it.out)
                {

                    // daca este nod care iese din curent
                    rezidual = matrice[curent][destinatie].capacitate - matrice[curent][destinatie].flow;
                    if(rezidual > 0)
                    {
                        tata[destinatie] = curent;
                        vizitat[destinatie] = true;
                        coada.push(destinatie);
                        //cout << curent << " -> " << destinatie << "  = " << rezidual << endl;
                        if(destinatie == n)
                            return true;
                    }

                }
                else
                {
                    // daca este nod care intra in curent
                    rezidual = matrice[destinatie][curent].flow;
                    if(rezidual > 0)
                    {

                        tata[destinatie] = -curent;
                        vizitat[destinatie] = true;
                        coada.push(destinatie);
                        //cout << destinatie << " ====> " << curent << "   = " << rezidual << endl;
                        if(destinatie == n)
                            return true;
                    }

                }



            }

        }

    }

    return false;



}


void revizuieste()
{

    //cout << "\n\n\n\nREVIZUIRE\n\n\n";
    int curent = n;
    int t = tata[n];
    int rezidual;
    int minim = 999999;
    while(t!=0)
    {
        if(t < 0)
        {
            rezidual = matrice[curent][-t].flow;
            t = -t;
            //if(rezidual == 0)
                //cout << -t << " -> " << curent << endl;
        }
        else
            rezidual = matrice[t][curent].capacitate - matrice[t][curent].flow;

        //cout << t << " -> " << curent << endl;
        minim = min(rezidual,minim);
        curent = t;
        t = tata[curent];
    }

    rezultat += minim;
    //cout << rezultat << "    minim = " << minim << endl;
    curent = n;
    t = tata[n];

    while(t!=0)
    {
        if(t < 0)
        {
            t = -t;
            matrice[curent][t].flow -= minim;
        }
        else
            matrice[t][curent].flow += minim;

        curent = t;
        t = tata[curent];
    }






}




int main()
{
    citire();
    while(BFS())
        revizuieste();

    int i;
    /*
        rezultat = 0;
    for(i=1;i<n;i++)
        if(matrice[i][n].capacitate > 0)
            rezultat += matrice[i][n].flow;

    */
    g << rezultat;
    //cout << rezultat;


}