#include <iostream>
#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();

   q.push(1);

    memset(use,0,sizeof(use));
    memset(ant,0,sizeof(ant));
 use[1]=1;

   while(!q.empty())
   { nod=q.front(); q.pop();

      for(i=0;i<v[nod].size();i++)
       { nod2=v[nod][i];

        if (!use[nod2] && ((c[nod][nod2]>0 && c[nod][nod2]>fol[nod][nod2]) || (!c[nod][nod2] && fol[nod2][nod])))
        { 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;
          // cout<<x<<" ";
           if (c[n1][n2]) res=min(res,c[n1][n2]-fol[n1][n2]);
           else res=min(res,fol[n2][n1]);
           x=ant[x]; //if (!ant[x]) cout<<x<<" ";
         }

          res=min(res,c[v[n][i]][n]);// cout<<"     "<<res<<"\n";
        x=v[n][i]; sol+=res;

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

         if (c[v[n][i]][n]) fol[v[n][i]][n]+=res;
          else fol[v[n][i]][n]-=res;
       }


 /* */

    g<<sol;
    return 0;
}