#include <iostream>
#include <fstream>
#define nmax 1014
#define inf 299999999
using namespace std;
long c[nmax][nmax],f[nmax][nmax];
int n,s,d,q[nmax],viz[nmax],l[nmax];

int abs(int x){if(x>0)return x;return -x;}
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int bfs(int x)
{int in,sf,i,y;
in=sf=0;
q[in]=x;
viz[x]=1;
  while(in<=sf && !viz[d])
    {y=q[in++];
    for(i=1;i<=n;i++)
      if(!viz[i])
        if(f[y][i]<c[y][i])
        {viz[i]=y;q[++sf]=i;}
        else
        if(f[i][y])
        {viz[i]=-y;q[++sf]=i;}

    }
return !viz[d];
}

void ek()
{int i,lg;
 long v;
    while(1)
    {
        for(i=1;i<=n;i++)viz[i]=0;
        if(bfs(1))return;
        lg=0;
        l[0]=d;
        v=inf;
        while(l[lg]!=s)
        {
            l[++lg]=abs(viz[l[lg-1]]);
            if(viz[l[lg-1]]>0)
                v=min(v,c[l[lg]][l[lg-1]]-f[l[lg]][l[lg-1]]);
                else v=min(v,f[l[lg-1]][l[lg]]);
        }

        while(lg)
        {if(viz[l[lg-1]]>0)
            f[l[lg]][l[lg-1]]+=v;
            else f[l[lg-1]][l[lg]]-=v;
            lg--;
        }

    }
}


int main()
{int m,i,x,y,cap;

    fin>>n>>m;
    s=1;d=n;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cap;
        c[x][y]=cap;
    }
    ek();
 long rez=0;
    for(i=1;i<=n;i++)
        rez+=f[i][n];
        fout<<rez;
}