#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, nd;
  while (1)
  {
    if (BFS()) return;
    q=0; T[q]=n;
    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];
}