#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
vector <int> a[1001];
int c[1001][1001],flux[10001][1001],n,m,viz[1001],coada[1001],s,d,minim,r;
int bfs()
{
    int i,prim,ultim,x,sw=0;
    for(i=1;i<=n;i++)
    {
        viz[i]=coada[i]=0;
    }
    viz[s]=-1;
    prim=ultim=1;
    coada[prim]=s;
    while(prim<=ultim)
    {
        x=coada[prim++];
        for(i=0;i<a[x].size();i++)
        {
            if(viz[a[x][i]]==0 && c[x][a[x][i]]>flux[x][a[x][i]])
            {
                if(a[x][i]!=d)
                {
                    viz[a[x][i]]=x;
                    ultim++;
                    coada[ultim]=a[x][i];
                }
                else
                {
                    sw=1;
                }
            }
        }
    }
    return sw;
}
void dinic()
{
    int i,nod;
    while(bfs()!=0)
    {
        for(i=0;i<a[d].size();i++)
        {
            if(viz[a[d][i]]!=0 && c[a[d][i]][d]>flux[a[d][i]][d])
            {
                viz[d]=a[d][i];
                minim=0x7fffffff;;
                nod=d;
                while(nod!=s)
                {
                    if(minim>c[viz[nod]][nod]-flux[viz[nod]][nod])
                    {
                        minim=c[viz[nod]][nod]-flux[viz[nod]][nod];
                    }
                    nod=viz[nod];
                }
                if(minim>0)
                {
                    r=r+minim;
                    nod=d;
                    while(nod!=s)
                    {
                        flux[viz[nod]][nod]+=minim;
                        flux[nod][viz[nod]]-=minim;
                        nod=viz[nod];
                    }
                }
            }
        }
    }
}
int main()
{
    int i,x,y,z;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        c[x][y]=z;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    s=1;
    d=n;
    dinic();
    g<<r;
    return 0;
}