#include <fstream>
#include <stdlib.h>
#include <string.h>
#define nmax 1005
#define mmax  5005
#define inf 110005
using namespace std;
fstream f1("maxflow.in", ios::in);
fstream f2("maxflow.out", ios::out);
long int fmax;
int n, m, aux[nmax],cap[nmax], viz[nmax], coada[nmax], pred[nmax], prim, ultim, k, s=1, d, ok=1, v[2*mmax];
long int  cost[nmax][nmax];
struct muchii
{
    int x, y;
}muc[mmax];
void citire()
{
    int i, x, y;
    long int c;
    f1>>n>>m;
    d=n;
    for(i=1; i<=m; i++)
    {
        f1>>muc[i].x>>muc[i].y>>c;
        aux[muc[i].x]++;
        aux[muc[i].y]++;
        cost[muc[i].x][muc[i].y]=c;
    }
    cap[1]=1;
    for(i=2; i<=n+1; i++)
    {
        cap[i]=cap[i-1]+aux[i-1];
        aux[i-1]=cap[i-1];
    }
    for(i=1; i<=m; i++)
    {
        x=muc[i].x;
        y=muc[i].y;

        v[aux[x]]=y;
        aux[x]++;

        v[aux[y]]=x;
        aux[y]++;
    }
}
void init_bfs()
{
    memset(viz, 0, sizeof(viz));
    viz[s]=1;
    prim=1;
    k=1;
    ultim=1;
    coada[prim]=s;
}
void upgrade()
{
    int nod;
    long int fmin=inf;
    nod=d;
    while(nod>1)
    {
        fmin=min(fmin, cost[pred[nod]][nod]);
        nod=pred[nod];
    }
    fmax+=fmin;

    nod=d;
    while (nod>1)
    {
         cost[pred[nod]][nod]-=fmin;
         cost[nod][pred[nod]]+=fmin;
         nod=pred[nod];
    }
}
int bfs()
{
   int i, cur, vec;
   ok=0;
   while(k!=0)
   {
      cur=coada[prim];
      prim++;
      k--;

      for(i=cap[cur]; i<cap[cur+1]; i++)
        if((!viz[v[i]])&&(cost[cur][v[i]]>0))
      {
          vec=v[i];
          pred[vec]=cur;
          if(vec==d) {ok=1; upgrade();}
          else
          {
              viz[vec]=1;
              ultim++;
              k++;
              coada[ultim]=vec;
          }
      }
   }
   return ok;
}
void edk()
{
    init_bfs();
    while(bfs())
    {
        init_bfs();
    }
    f2<<fmax;
}
int main()
{
    citire();///+creare graf rezidual
    edk();
    return 0;
}