#include<fstream>
#include <queue>
#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]={0},cost[NMX][NMX]={0};
int bfs(){
    int i,x;
    for(int i=0;i<=n;i++) tata[i]=viz[i]=0;
    queue<int> c;
    int s=0;
     c.push(s);
     viz[s]=1;
     while(c.size()>0){
             x=c.front();
             c.pop();
             for(auto y:l[x]){
                  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(auto y:lin[x]){

                      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(){
     ifstream fs("maxflow.in");

     int i,x,y,j;
     long c;

     fs>>n>>m;
     for(i=0;i<m;i++){
         fs>>x>>y>>c;
         l[x-1].push_back(y-1);
         lin[y-1].push_back(x-1);
         cost[x-1][y-1]=c;
     }

     fs.close();
     long fmax=0;
     while(bfs()){

          long iP=110000;
          int t=n-1;

          while(t!=0)  {
               if(tata[t]>=0){
                  if(cost[tata[t]][t]-f[tata[t]][t]<iP)
                       iP= cost[tata[t]][t]-f[tata[t]][t];
                  t=tata[t];
               }
               else  {
                    if( f[t][-tata[t]]<iP)
                       iP= f[t][-tata[t]];
                    t=-tata[t];
                }

          }
          t=n-1;
          while(t!=0)  {
               if(tata[t]>=0 ){
                   f[tata[t]][t]+=iP;
                   t=tata[t];
                   }
                else{
                   f[t][-tata[t]]-=iP;
                   t=-tata[t];
                   }
          }
          fmax+=iP;

     }
     ofstream g("maxflow.out");
     g<<fmax;
     g.close();

     return 0;
}