#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int n,m,c[1005][1005],fol[1005][1005],use[1005],ant[1005],mn[1005],inf=2147000000,sol=0;


 vector <int> v[1005];
 queue <int> q;

void BFS(int x)
{ int nod,nod2,i;

   while(!q.empty()) q.pop();

   memset(use,0,sizeof(use));
   memset(ant,0,sizeof(ant));

   q.push(1); use[1]=1;

   while(!q.empty())
   { nod=q.front(); q.pop();
       if (nod==n) return;
      for(i=0;i<v[nod].size();i++)
       { nod2=v[nod][i];

        if (!use[nod2] && c[nod][nod2]>fol[nod][nod2])
        { use[nod2]=1;
          q.push(nod2);
          ant[nod2]=nod;
        }

       }
   }

}

int main()
{ int i,x,y,cap,res,n1,n2;
    f>>n>>m;

    for(i=1;i<=m;i++)
    { f>>x>>y>>cap;
      c[x][y]=cap;
        v[x].push_back(y);
        v[y].push_back(x);
    }


   for(BFS(1);use[n]>0;BFS(1))
    for(i=0;i<v[n].size();i++)
     if (use[v[n][i]] && c[v[n][i]][n]>fol[v[n][i]][n])
      {
        x=v[n][i]; res=inf;

         while(ant[x])
         { n1=ant[x]; n2=x;
           res=min(res,c[n1][n2]-fol[n1][n2]);
           x=ant[x];
         }
          res=min(res,c[v[n][i]][n]-fol[v[n][i]][n]);

        x=v[n][i]; sol+=res;

         while(ant[x])
         { n1=ant[x]; n2=x;
            fol[n1][n2]+=res;
            fol[n2][n1]-=res;
           x=ant[x];
         }

         fol[v[n][i]][n]+=res;
         fol[n][v[n][i]]-=res;

       }

     g<<sol;

    return 0;
}