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

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

int n;
vector < vector < int > > V;
int FMAX[1001][1001];
int F[1001][1001];
bool drum;
vector < int > Q;
bool VIZ[1001];
int T[1001];

void citire()
{
    int m,i,x,y,f;
    fin>>n>>m;
    V.resize(n+1);
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>f;
        V[x].push_back(y);
        V[y].push_back(x);
        FMAX[x][y]=f;
    }
}

void bfs()
{
    drum = false;
    memset(VIZ,0,sizeof(VIZ));
    Q.clear();
    Q.push_back(1);
    auto it2 = V[1].begin();
    VIZ[1]=true;
    T[1]=0;
    int nod;
    for(auto it = Q.begin(); it != Q.end(); it ++)
    {
        nod=*it;
        for(it2 = V[nod].begin(); it2 != V[nod].end(); it2 ++)
        {
            if(F[nod][*it2]<FMAX[nod][*it2] && !VIZ[*it2])
            {
                Q.push_back(*it2);
                VIZ[*it2]=true;
                T[*it2]=nod;
                /*if(*it2 == n)
                {
                    drum=true;
                    return ;
                }*/
            }

        }
    }
}

void rezolvare()
{
    Q.reserve(100008);
    bfs();
    int nod,fmax,i;
    FMAX[0][1]=2000000000;
    while(VIZ[n])
    {
        for(i=1; i<n; i++)
            if(F[i][n]<FMAX[i][n] && VIZ[i])
            {
                T[n]=i;
                fmax = 2000000000;
                nod = n;
                while(nod != 1)
                {
                    fmax=min(fmax,FMAX[T[nod]][nod]-F[T[nod]][nod]);
                    nod=T[nod];
                }
                nod = n;
                while(nod != 1)
                {
                    F[T[nod]][nod]+=fmax;
                    F[nod][T[nod]]-=fmax;
                    nod = T[nod];
                }
            }
        bfs();
    }
}

void afisare()
{
    int i,s=0;
    for(i=1; i<n; i++)
        s+=F[i][n];
    fout<<s;
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}