#include<iostream>
#include<fstream>
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
long C[1001][1001],F[1001][1001];
int viz[1001],L[1001],k,n;
int modul(int a)
{
    if(a<0)return -a;
    return a;
}
int minim(int a,int b)
{
    if(a<b)return a;
    return b;
}
int parcurgere()
{
    int Q[1001],p,u,x,i;
    p=u=1;
    Q[1]=1;
    while(viz[n]==0&&p<=u)
    {
        x=Q[p++];
        for(i=2;i<=n;i++)
            if(viz[i]==0)
                 if(F[x][i]<C[x][i])
                     {
                         Q[++u]=i;
                         viz[i]=x;
                     }
                 else if(F[i][x]>0)
                    {
                        Q[++u]=i;
                        viz[i]=-x;
                    }
    }
    if(viz[n]==0)return 1;
    return 0;
}
int main()
{
    int m,i,ok=0,x,y;
    long a,b,v,z,S=0;

    f>>n>>m;
    for(i=1;i<=m;i++)
       {f>>x>>y>>z;
        C[x][y]=z;
       }
    do
    {
        a=b=110000;
        if(parcurgere()==0)
           {
               L[1]=n;
               k=1;
               while(L[k]!=1)
                  {
                      k++;
                      L[k]=modul(viz[L[k-1]]);
                      if(viz[L[k-1]]>0)
                           a=minim(a,C[L[k]][L[k-1]]-F[L[k]][L[k-1]]);
                      else b=minim(b,F[L[k-1]][L[k]]);
                  }
                v=minim(a,b);
                for(i=k;i>1;i--)
                  if(viz[L[i-1]]>0)F[L[i]][L[i-1]]+=v;
                  else F[L[i-1]][L[i]]-=v;
           }
        else ok=1;
        for(i=1;i<=n;i++)viz[i]=0;
    }
    while(ok==0);
    for(i=1;i<=n;i++)S=S+F[i][n];
    g<<S;
    f.close();
    g.close();
    return 0;
}