#include <cstdio>
#include <cassert>
#include <queue>
#define Nmax 1005
#define InFile "maxflow.in"
#define OutFile "maxflow.out"

using namespace std;

int n, m;
int viz[Nmax], T[Nmax];
int F[Nmax][Nmax], C[Nmax][Nmax];

void read();
void EdmondsKarp();
int BFS();
inline int Abs (int x) {if (x>0) return x; return -x;}

int main()
{
  int i, sum=0;
  assert (freopen (InFile, "r", stdin));
  assert (freopen (OutFile, "w", stdout));
  read();
  EdmondsKarp();
  for (i=1; i<=n; i++)
    sum+=F[i][n];
  printf ("%d\n", sum);
  return 0;
}

void read()
{
  int i, x, y, c;
  scanf ("%d %d\n", &n, &m);
  for (i=1; i<=m; i++)
  {
    scanf ("%d %d %d\n", &x, &y, &c);
    C[x][y]=c;
  }
}

void EdmondsKarp()
{
  int i, a, b, v, q, x, nd;
  while (1)
  {
    if (BFS()) return;
    for (x=1; x<=n; x++)
      if (F[x][n]<C[x][n])
      {
        q=0; T[q]=n;
        q=1; T[q]=x;
        a=b=(int)1e9;
        while (T[q]!=1)
        {
          q++; nd=T[q-1];
          T[q]=Abs (viz[nd]);
          if (viz[nd]>0)
            a=min (a, C[T[q]][nd]-F[T[q]][nd]);
          else
            if (viz[nd]<0)
              b=min (b, F[nd][T[q]]);
        }
        v=min(a, b);
        for (i=q; i>0; i--)
          if (viz[T[i-1]]>0)
            F[T[i]][T[i-1]]+=v;
          else
            if (viz[T[i-1]]<0)
              F[T[i-1]][T[i]]-=v;
      }
  }
}

int BFS ()
{
  int i, x;
  queue <int> Q;
  for (i=1; i<=n; i++) viz[i]=0;
  Q.push(1); viz[1]=1;
  while (!Q.empty() && !viz[n])
  {
    x=Q.front(); Q.pop();
    for (i=1; i<=n; i++)
      if (!viz[i])
        if (F[x][i]<C[x][i])
          viz[i]=x, Q.push(i);
        else
          if (F[i][x]>0)
            viz[i]=-x, Q.push(i);
  }
  return !viz[n];
}