#include <cstdio>
#include <queue>
#define NMAX 1001
#define INF 1<<30
using namespace std;
FILE* fin=fopen("maxflow.in","r");
FILE* fout=fopen("maxflow.out","w");
int n,m,mark[NMAX];
int cap[NMAX][NMAX],flux[NMAX][NMAX],gint[NMAX],gext[NMAX],s,f,fmax;
void citire();
void rezolvare();
int minim(int a,int b) { if (a<b) return a; return b;}
bool marcheaza();
int main()
{
int i;
    citire();
    for (i=1; i<=n; i++)
    {
        if (!gint[i]) s=i;
        if (!gext[i]) f=i;
    }
    rezolvare();
    return 0;
}
void citire()
{
    int i,x,y,z;
    fscanf(fin,"%d %d",&n,&m);
    for (i=1; i<=m; i++)
    {
        fscanf(fin,"%d %d %d",&x,&y,&z);
        cap[x][y]=z;
        gint[y]++; gext[x]++;
        //if (!cap[y][x]) cap[y][x]=-1*z;
    }
}
void rezolvare()
{
    int nod,ok,v1,v2,val,v;
    while (1==1)
    {
        ok=marcheaza();
        if (!ok) break;
        nod=f;
        v1=v2=INF;
        while (mark[nod]!=INF)
        {
            if (mark[nod]>0) //sens direct
            {
                val=cap[mark[nod]][nod] - flux[mark[nod]][nod];
                if (val>0 && v1>val) v1=val;
            }
            else
            {
                val=flux[-1*mark[nod]][nod];
                if (val>0 && v2>val) v1=val;
            }
            if (mark[nod]<0) nod=-1*mark[nod];
            else nod=mark[nod];
        }
        v=minim(v1,v2);
        nod=f;
        while (mark[nod]!=INF)
        {
            if (mark[nod]>0) //sens direct;
                flux[mark[nod]][nod]+=v;
            else flux[-1*mark[nod]][nod]-=v;
            if (mark[nod]<0) nod=-1*mark[nod];
            else nod=mark[nod];
        }
        fmax+=v;
    }
    fprintf(fout,"%d\n",fmax);
}
bool marcheaza()
{
    int i,nod;
    queue <int> q;
    for (i=1; i<=n; i++) mark[i]=0;
    mark[s]=INF;
    q.push(s);
    while (!q.empty())
    {
        nod=q.front(); q.pop();
        for (i=1; i<=n; i++)
        {
            if (!mark[i])
            {
                if (flux[nod][i]<cap[nod][i])
                {
                    mark[i]=nod; q.push(i); if (i==n) return 1;
                }
                else
                {
                    if (flux[i][nod]>0)
                    {
                        mark[i]=-1*nod; q.push(i);
                        if (i==n) return 1;
                    }
                }
            }
//            if (cap[nod][i]>0 && cap[nod][i]!=flux[nod][i])
//            {
//                mark[i]=nod;
//                q.push(i);
//                if (i==f) return 1;
//            }
//            if (cap[nod][i]<0 && -1*cap[nod][i]!=flux[nod][i])
//            {
//                mark[i]=-1*nod;
//                q.push(i);
//                if (i==f) return 1;
//            }
        }
    }
    return 0;
}