#include <fstream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#define nmax 1005
using namespace std;
fstream f1("maxflow.in", ios::in);
fstream f2("maxflow.out", ios::out);
int n, m, cap[nmax][nmax], flux[nmax][nmax], S, D, prim, ultim, k, coada[nmax], viz[nmax], l[nmax];
long long fmax;
vector<int> v[nmax];
//Dinic
void citire()
{
    int i, x, y, c;
    f1>>n>>m;
    S=1; D=n;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        cap[x][y]=c;
        v[x].push_back(y);
        v[y].push_back(x);//poti merge si pe muchiile inverse
    }
}
int bfs()
{
    int nod;
    memset(viz, 0, sizeof(viz));
    memset(l, 0, sizeof(l));
    prim=ultim=k=1;
    coada[ultim]=S;
    viz[S]=1;
    while(k!=0)
    {
        nod=coada[prim];
        prim++; k--;
        for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
            if((!viz[*it])&&(cap[nod][*it]-flux[nod][*it]>0))
        {
            viz[*it]=1;
            ultim++;k++;
            coada[ultim]=*it;
            l[*it]=nod;
            if(*it==n) return 1;
        }
    }
    return 0;
}
void amelioreaza_drum()
{
    int i, mini=110005, nod;
    for(auto it=v[D].begin(); it!=v[D].end(); ++it)
        if(viz[*it]&&(cap[*it][D]-flux[*it][D]>0)) ///nodul sa fie vizitat si cu muchie ameliorabila catre D
    {
        nod=*it;///vecin cu sursa
        mini=min(mini, cap[nod][D]-flux[nod][D]);

        if(l[nod]!=0) ///face parte dintr-un drum de ameliorare
        {
            for(i=nod; i!=S; i=l[i])
            if(mini> cap[l[i]][i]-flux[l[i]][i])
                mini=cap[l[i]][i]-flux[l[i]][i];
             if(mini==0) continue;

            flux[nod][D]+=mini;
            flux[D][nod]-=mini;
            for(i=nod; i!=S; i=l[i])
            {
                flux[l[i]][i]+=mini;
                flux[i][l[i]]-=mini;
            }
            fmax+=mini;
        }
    }
}
int main()
{
    citire();
    while(bfs()) ///cat timp exista drum de ameliorare
    amelioreaza_drum();
    f2<<fmax;
    return 0;
}