#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;

 struct vec
 { int y,cap; };

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

void BFS(int x)
{ int nod,nod2,i;
   while(!q.empty()) q.pop();
   q.push(1); mn[1]=inf;
    memset(use,0,sizeof(use));
    memset(ant,0,sizeof(ant));
 use[1]=1;
   while(!q.empty())
   { nod=q.front(); q.pop();
     // cout<<nod<<"\n";
      for(i=0;i<v[nod].size();i++)
       { nod2=v[nod][i].y;

        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;
          if (c[nod][nod2]) mn[nod2]=min(mn[nod],c[nod][nod2]-fol[nod][nod2]);
           else mn[nod2]=min(mn[nod],fol[nod2][nod]);
         if (nod2==n) return;
        }

       }

   }

}

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

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


    for(;;)
    {
        BFS(1); //cout<<"end"<<"\n";
        if (!use[n]) break;
        x=n; res=mn[x];

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

    }

    for(i=0;i<v[1].size();i++)
     sol+=fol[1][v[1][i].y];

    g<<sol;
    return 0;
}