#include <queue>
#include<stdio.h>
#include <cstring>
#define NMX 10001
using namespace std;
int tata[NMX],n,m,viz[NMX];
vector<int> l[NMX];
vector<int> lin[NMX]; 
long f[NMX][NMX],cost[NMX][NMX];
int bfs(){
    int i,x;
    memset(tata,0,sizeof(tata));
    memset(viz,0,sizeof(viz));
    queue<int> c;
    int s=0;
     c.push(s);
     viz[s]=1;
     while(c.size()>0){
             x=c.front();
             c.pop();
             for(i=0;i<l[x].size();i++){  
                  int y=l[x][i];                                              
                  if(viz[y]==0 && f[x][y]<cost[x][y]){
                      tata[y]=x;
                      if(y==n-1)
                          return 1;
                      c.push( y);
                      viz[y]=1;
                  } 
               }  
                for(i=0;i<lin[x].size();i++){  
                      int y=lin[x][i];                                              
                      if(viz[y]==0 && f[y][x]>0){
                          tata[y]=-x;
                          if(y==n-1)
                              return 1;
                          c.push(y);
                          viz[y]=1;
                      } 
               }
       } 
       return 0;       
}

int main(){
     FILE *fs,*g;
     int i,x,y,j;
     long c;
     
     fs=fopen("maxflow.in","r");
     fscanf(fs,"%d %d",&n,&m);
     for(i=0;i<m;i++){
         fscanf(fs,"%d %d %ld",&x,&y,&c);
         l[x-1].push_back(y-1);
         lin[y-1].push_back(x-1);
         cost[x-1][y-1]=c;
     }
   
     fclose(fs);
     long fmax=0;
     while(bfs()){
         
          long cresc=110000; 
          int t=n-1;     
          
          while(t!=tata[t])  {
               if(tata[t]>=0){
                  if(cost[tata[t]][t]-f[tata[t]][t]<cresc)
                       cresc= cost[tata[t]][t]-f[tata[t]][t];  
                  t=tata[t];     
               }   
               else  {  
                    if( f[t][-tata[t]]<cresc)
                       cresc= f[t][-tata[t]];
                    t=-tata[t];
                }
              
          }  
          t=n-1;
          while(t!=tata[t])  {
               if(tata[t]>=0 ){
                   f[tata[t]][t]+=cresc;  
                   t=tata[t];
                   }   
                if(tata[t]<0 ){
                   f[t][tata[t]]-=cresc;
                   t=-tata[t];
                   }   
          }              
          fmax+=cresc;
         
     }        
     g=fopen("maxflow.out","w");
     fprintf(g,"%ld",fmax);
     fclose(g);
                                  
     return 0;   
}