#include<fstream.h>
#define INF 1000000
#define N 1001
int n,m,k,deg[N]={0},g1[N][N],b[5*N],c[5*N],e[5*N];
long flow[N][N]={0},d[N],g2[N][N];
long min(long a,long b)
{if(a<b)
      return a;
return b;}
long EK(int g1[N][N],long g2[N][N],int deg[N],int n,int source,int sink,long flow[N][N],long d[N])
{long pre[N],que[N],p,q,t,i,j,k,l;
while(1)      
       {for(k=1;k<=n;k++)
               pre[k]=-1;
       d[source]=INF;
       p=q=0;
       que[q++]=source;
       while(p<q&&pre[sink]<0)
               {t=que[p++];
               for(i=1;i<=deg[t];i++)
               if(pre[g1[t][i]]<0&&(j=g2[t][g1[t][i]]-flow[t][g1[t][i]])!=0)
                       {pre[que[q++]=g1[t][i]]=t;
                       d[g1[t][i]]=min(d[t],j);}}
       if(pre[sink]<0)
               break;
       for(l=sink;l!=source;l=pre[l])
               {flow[pre[l]][l]+=d[sink];
               deg[pre[l]]++;
               g1[pre[l]][deg[pre[l]]]=l;
               deg[l]++;
               g1[l][deg[l]]=pre[l];
               flow[l][pre[l]]-=d[sink];}}
for(j=0,i=1;i<=n;i++)
       j+=flow[source][i];
return j;}
int main()
{ifstream x("maxflow.in");
ofstream y("maxflow.out");
x>>n>>m;
for(k=1;k<=m;k++)
     {x>>b[k]>>c[k]>>e[k];
     deg[b[k]]++;
     g1[b[k]][deg[b[k]]]=c[k];
     g2[b[k]][c[k]]=e[k];}
y<<EK(g1,g2,deg,n,1,n,flow,d);    
x.close();
y.close();
return 0;}