#include <fstream>

using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int n,m;
struct nod
{int info;
 nod *urm;

} *g[1001];
void Addelem(nod *&prim,int info)
{ nod *q=new nod;
  q->info=info;
  q->urm=prim;
  prim=q;
}
int ok;

int cc[1001][1001],f[1001][1001];
void BFS(int x)
{
   int c[1000],t[1000],viz[1000]={0},pr,ul;
   pr=ul=1;
   c[1]=x;
   viz[1]=1;
   t[1]=0;
   int nodcurent;
   ok=0;
   while(pr<=ul)
   { nodcurent=c[pr];


      for(nod*p=g[nodcurent];p!=NULL;p=p->urm)
      {
        if(viz[p->info]==0&&cc[nodcurent][p->info]-f[nodcurent][p->info]>0)
          {
            t[p->info]=nodcurent;
            if(p->info==n)  {ok=1;break;}
            ul++;
            c[ul]=p->info;
            viz[p->info]=1;
          }
      }
      if(ok==1) break;
     pr++;
   }
   if(ok==1)
   {int cpr=n;
   int dmin=2000000000;
   while(t[cpr]!=0)
   {  if(cc[t[cpr]][cpr]-f[t[cpr]][cpr]<dmin) dmin=cc[t[cpr]][cpr]-f[t[cpr]][cpr];
      cpr=t[cpr];
   }
   cpr=n;
    while(t[cpr]!=0)
   {  f[t[cpr]][cpr]+=dmin;
      //f[c[cpr]][c[t[cpr]]]=f[c[cpr]][c[t[cpr]]]-dmin;
      f[cpr][t[cpr]]=-f[t[cpr]][cpr];
      cpr=t[cpr];
   }
   }
}
int main()
{ fin>>n>>m;
 int i,x,y,z;
   for(i=1;   i<=m;  i++)
   { fin>>x>>y>>z;
     Addelem(g[x],y);
     Addelem(g[y],x);
      cc[x][y]=z;
   }
ok=1;

while(ok) BFS(1);
int fmax=0;
for(nod*p=g[n];p!=NULL;p=p->urm)
fmax+=-f[n][p->info];
fout<<fmax;
    return 0;
}