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

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

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


int n,m;
queue<int> coada;
int tata[1001];
dual matrice[1001][1001];
int viz[1001];
int rezultat = 0;


void citire()
{
    int i,j;

    f>> n >> m;
    for(i=1;i<=n;i++)
        viz[i] = 0;

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            matrice[i][j].flow = -1;
            matrice[i][j].capacitate = -1;
        }

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


bool BFS()
{

    //cout << "\n\n\nBFS\n";
    int start,i;
    for(i=1;i<=n;i++)
        viz[i]=tata[i]=0;
    coada = queue<int>();
    coada.push(1);
    while(!coada.empty())
    {
        start = coada.front();
        coada.pop();
        viz[start] = 1;
        for(i=1;i<=n;i++)
            if(matrice[start][i].capacitate>0 && viz[i] == 0)
                if(matrice[start][i].capacitate - matrice[start][i].flow > 0)
            {
                //cout << "matrice[" << start << "][" << i << "].liber = " << matrice[start][i].capacitate - matrice[start][i].flow << endl;
                coada.push(i);
                viz[i]=1;
                tata[i]=start;
                if(i == n)
                    return true;
            }
        for(i=1;i<=n;i++)
            if(matrice[i][start].capacitate>0 && viz[i] == 0)
                if(matrice[i][start].flow > 0)
            {
                //cout << "matrice[" << i << "][" << start << "].flow = " << matrice[i][start].flow << endl;
                coada.push(i);
                viz[i]=1;
                tata[start]= -i;
                if(i == n)
                    return true;
            }
    }
    return false;
}


void revizuieste()
{
    int t = tata[n];
    int curent = n;
    int minim = 999999;
    while(t != 0)
    {

        if(t<0)
        {
            minim = min(matrice[-t][curent].capacitate - matrice[-t][curent].flow,minim);
            //cout << curent << " - " << t << " == " << matrice[-t][curent].capacitate - matrice[-t][curent].flow << endl;
        }
        else
        {
            //cout << curent << " - " << t << " == " << matrice[t][curent].capacitate - matrice[t][curent].flow << endl;
            minim = min(matrice[t][curent].capacitate - matrice[t][curent].flow,minim);
        }


        if(t<0)
        {
            curent = -t;
            t = tata[curent];
        }
        else
        {
            curent = t;
            t = tata[curent];
        }
    }
    //cout << "minim = " << minim << endl;
    rezultat += minim;
    //cout << rezultat << endl;
    t = tata[n];
    curent = n;
    while(t != 0)
    {
        if(t<0)
        {
            matrice[-t][curent].flow -= minim;
            curent = -t;
            t = tata[curent];
        }
        else
        {
            matrice[t][curent].flow += minim;
            curent = t;
            t = tata[curent];
        }
    }


}




int main()
{
    citire();
    while(BFS())
        revizuieste();
    g << rezultat;



}