#include<fstream>
#include<stdlib.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int n,m,cost[1001][1001],flux[1001][1001],v[1001];
struct nod{
   int inf;
   nod *urm;
}*L[1001];
void adaugsf(nod *&vf,int val){
    nod *q;
    q=new nod;
    q->inf=val;
    q->urm=vf;
    vf=q;
}
int BFS(){
   int i,coada[1001],p,u,x;
   nod *q;
   p=u=1;
   coada[p]=1;v[1]=1;
   while(p<=u && v[n]==0){
      x=coada[p];
      q=L[x];
      while(q!=0){
        if (v[q->inf]==0){
          if (flux[x][q->inf]<cost[x][q->inf]){
            v[q->inf]=x;u++;
            coada[u]=q->inf;
          }
            else
              if (flux[q->inf][x]>0){
                v[q->inf]=-x;
                u++;coada[u]=q->inf;
              }
        }
       q=q->urm;
      }
      p++;
   }
   return v[n];
}
void Edmonds_Karp(){
    int lant[1001],a,b,len,i,val;
   do{
    for (i=1;i<=n;i++)
        v[i]=0;
    if (BFS()==0) return;
    lant[0]=n;len=0;a=900000000;b=900000000;
    while(lant[len]!=1){
        len++;
        lant[len]=abs(v[lant[len-1]]);
        if (v[lant[len-1]]>0) a=min(a,cost[lant[len]][lant[len-1]]-flux[lant[len]][lant[len-1]]);
          else
            b=min(b,flux[lant[len-1]][lant[len]]);
    }
    val=min(a,b);
    for (i=len;i>0;i--)
        if (v[lant[i-1]]>0) flux[lant[i]][lant[i-1]]+=val;
             else
                flux[lant[i-1]][lant[i]]-=val;
   }while(0<1);
}
int main(){
    fin>>n>>m;
    int i,a,b;
    for (i=1;i<=n;i++)
        L[i]=0;
    for (i=1;i<=m;i++){
        fin>>a>>b;
        fin>>cost[a][b];
        adaugsf(L[a],b);
    }
   fin.close();
   Edmonds_Karp();
   int mflow=0;
   for (i=1;i<=n;i++)
    mflow=mflow+flux[i][n];
   fout<<mflow;
   fout.close();
   return 0;
}