#include <cstdio>
#include <cassert>
#include <queue>
#include <vector>
#define Nmax 1005
#define INF (int)1e9
#define InFile "maxflow.in"
#define OutFile "maxflow.out"
#define pb push_back

using namespace std;

int n, m, nr=0;
int viz[Nmax], T[Nmax], vd[Nmax];
int F[Nmax][Nmax], C[Nmax][Nmax];
vector <int> A[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; A[x].pb (y);
    if (y==n) vd[++nr]=x;
  }
}

void EdmondsKarp()
{
  int i, j, a, b, v, q, x, nd;
  while (1)
  {
    if (BFS()) return;
    for (j=1; j<=nr; j++)
    {
      x=vd[j];
      if (viz[x] && F[x][n]<C[x][n])
      {
        q=0; T[q]=n;
        if (F[x][n]<C[x][n]) 
          viz[n]=x;
        a=b=INF;
        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, y, lg;
  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();
    lg=A[x].size();
    for (i=0; i<lg; i++)
    {
      y=A[x][i];
      if (!viz[y])
        if (F[x][y]<C[x][y])
          viz[y]=x, Q.push(y);
        else
          if (F[y][x]>0)
            viz[y]=-x, Q.push(y);
    }
  }
  return !viz[n];
}