#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int a[1001][1001],n,m,flux[1001][1001],c[1001],viz[1001],s,d;
int bfs()
{
    int i,prim,ultim,x;
    prim=ultim=1;
    c[prim]=1;
    viz[s]=1;
    while(prim<=ultim && viz[n]==0)
    {
        x=c[prim++];
        for(i=1;i<=n;i++)
        {
            if(viz[i]==0)
            {
                if(a[x][i]>flux[x][i])
                {
                    viz[i]=x;
                    ultim++;
                    c[ultim]=i;
                }
                else
                {
                    if(flux[i][x]>0)
                    {
                        viz[i]=-x;
                        ultim++;
                        c[ultim]=i;
                    }
                }
            }
        }
    }
    return viz[d];
}
void ek()
{
    int i,t[1001],minim1,minim2,nr,minim;
    while(bfs()!=0)
    {
        t[1]=d;
        nr=1;
        minim1=minim2=5000001;
        while(t[nr]!=1)
        {
            nr++;
            t[nr]=abs(viz[t[nr-1]]);
            if(viz[t[nr-1]]>0)
            {
                minim1=min(minim1,a[t[nr]][t[nr-1]]-flux[t[nr]][t[nr-1]]);
            }
            else
            {
                if(viz[t[nr-1]]<0)
                {
                    minim2=min(minim2,flux[t[nr-1]][t[nr]]);
                }
            }
        }
       minim=min(minim1,minim2);
       for(i=nr;i>=2;i--)
       {
          if(viz[t[i-1]]>0)
          {
            flux[t[i]][t[i-1]]+=minim;
          }
          else
          {
            flux[t[i-1]][t[i]]-=minim;
          }
       }
       for(i=1;i<=n;i++)
       {
           viz[i]=c[i]=0;
       }
    }
}
int main()
{
    int i,x,y,z,r=0;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        a[x][y]=z;
    }
    s=1;d=n;
    ek();
    for(i=1;i<=n;i++)
    {
        r=r+flux[i][d];
    }
    g<<r;
    return 0;
}