#include <iostream>
#include <vector>
#include <queue>

#define MAXN 1000
#define MAXM 5000
#define MAXLOG10 10
#define BUFSIZE (128 * 1024)
using namespace std;

struct edge{
  int b, direction, indForEdgeCalc;
};

struct edgeCalc{
  int maxFlux, usedFlux;
};

struct node{
  bool isCloseToEnd;
  int indForCloseToEnd;
  int lvl;
  int totFlux;
  vector <edge> edges;
};

FILE *fin, *fout;
int p10[MAXLOG10 + 1] = { 0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
int rpos; char rbuf[BUFSIZE];
int wpos; char wbuf[BUFSIZE];

static inline void initRead() {
  rpos = BUFSIZE - 1;
}

static inline char readChar() {
  if ( !(rpos = (rpos + 1) & (BUFSIZE - 1)) )
    fread( rbuf, 1, BUFSIZE, fin );
  return rbuf[rpos];
}

int readInt() {
  char ch;
  int res = 0, semn = 1;

  ch = readChar();
  while ( isspace(ch) )
    ch = readChar();
  if ( ch == '-' ) {
    semn = -1;
    ch = readChar();
  }
  do
    res = 10 * res + ch - '0';
  while ( isdigit( ch = readChar() ) );

  return semn * res;
}

node graph[MAXN];
edgeCalc edges[MAXM];
bool isInOp[MAXN];
int sizeEdgeCalc;
queue <int> op;

void addEdge(const int a, const int b, const int maxFlux, const int n) {
  graph[a].edges.push_back({b, 1, sizeEdgeCalc});
  graph[b].edges.push_back({a, -1, sizeEdgeCalc});
  if ( b == n - 1 ) {
    graph[a].isCloseToEnd = true;
    graph[a].indForCloseToEnd = sizeEdgeCalc;
  }
  edges[sizeEdgeCalc].maxFlux = maxFlux;
  sizeEdgeCalc++;
}

int findMinLvl(int pos) {
  int ans;
  ans = MAXN + 1;

  for ( edge i : graph[pos].edges ) {
    if ( graph[i.b].lvl < ans && ((i.direction == 1 && edges[i.indForEdgeCalc].usedFlux < edges[i.indForEdgeCalc].maxFlux) || (i.direction == -1 && edges[i.indForEdgeCalc].usedFlux)) )
      ans = graph[i.b].lvl;
  }

  return ans;
}

void initialise(int n) {
  graph[0].lvl = n;
  for ( edge i : graph[0].edges ) {
    edges[i.indForEdgeCalc].usedFlux = edges[i.indForEdgeCalc].maxFlux;
    graph[i.b].totFlux += edges[i.indForEdgeCalc].maxFlux;
    if ( i.b != n - 1 ) {
      op.push(i.b);
      isInOp[i.b] = true;
    }
  }
}

void pushVol(int pos, int n) {
  int toAdd, startFlux;

  if ( graph[pos].isCloseToEnd && graph[pos].lvl ) {
    if ( edges[graph[pos].indForCloseToEnd].maxFlux > edges[graph[pos].indForCloseToEnd].usedFlux ) {
      toAdd = min(graph[pos].totFlux, edges[graph[pos].indForCloseToEnd].maxFlux - edges[graph[pos].indForCloseToEnd].usedFlux);
      edges[graph[pos].indForCloseToEnd].usedFlux += toAdd;
      graph[n - 1].totFlux += toAdd;
      graph[pos].totFlux -= toAdd;
    }
  }
  for ( edge i : graph[pos].edges ) {
    if ( graph[i.b].lvl < graph[pos].lvl ) {
      startFlux = graph[i.b].totFlux;
      if ( i.direction > 0 && edges[i.indForEdgeCalc].maxFlux > edges[i.indForEdgeCalc].usedFlux ) {
        toAdd = min(graph[pos].totFlux, edges[i.indForEdgeCalc].maxFlux - edges[i.indForEdgeCalc].usedFlux);
        edges[i.indForEdgeCalc].usedFlux += toAdd;
        graph[i.b].totFlux += toAdd;
        graph[pos].totFlux -= toAdd;
      } else if ( i.direction < 0 && edges[i.indForEdgeCalc].usedFlux ) {
        toAdd = min(graph[pos].totFlux, edges[i.indForEdgeCalc].usedFlux);
        edges[i.indForEdgeCalc].usedFlux -= toAdd;
        if ( i.b )
          graph[i.b].totFlux += toAdd;
        graph[pos].totFlux -= toAdd;
      }
      if ( startFlux == 0 && graph[i.b].totFlux > 0 && i.b && i.b != n - 1 && !isInOp[i.b] ) {
        op.push(i.b);
        isInOp[i.b] = true;
      }
    }
    if ( !graph[pos].totFlux )
      break;
  }
}

void calcAns(int n) {
  int pos, x;

  initialise(n);

  x = 0;
  while ( op.size() ) {
    pos = op.front();
    op.pop();
    isInOp[pos] = false;
    pushVol(pos, n);
    if ( graph[pos].totFlux ) {
      graph[pos].lvl = findMinLvl(pos) + 1;
      op.push(pos);
    }
    x++;
  }
}

int main() {
  fin = fopen("maxflow.in", "r");
  fout = fopen("maxflow.out", "w");
  initRead();

  int n, m, i, a, b, flux;

  n = readInt();
  m = readInt();

  for ( i = 0; i < m; i++ ) {
    a = readInt();
    b = readInt();
    flux = readInt();
    a--;
    b--;

    addEdge(a, b, flux, n);
  }

  calcAns(n);

  fprintf(fout, "%d\n", graph[n - 1].totFlux);

  fclose(fin);
  fclose(fout);

  return 0;
}