#include <fstream>
#include <climits>

using namespace std;

struct Nod {
  int n;
  Nod* pred;
  Nod* urm;
};

#define N 1001

int C[N][N];
int F[N][N];
int excess[1000], height[1000], seen[1000], n, m;
Nod* s1;
Nod* s2;
ofstream fout ("maxflow.out");

void push(int u, int v) {
  int send;

  send = min(excess[u], C[u][v] - F[u][v]); // atat se poate trimite prin conducta (u,v)
  F[u][v] += send;
  F[v][u] -= send;
  excess[u] -= send;
  excess[v] += send;
}

void relabel(int u) { // se gaseste cea mai mica inaltime care face posibila o ridicare, daca o ridicare e posibila
  int min_height = height[u];

  for (int v = 1; v <= n; v++) // pentru toti vecinii lui u
    if (C[u][v]-F[u][v] > 0)
      min_height = min(min_height, height[v]);
  height[u] = min_height + 1; // se ridica deasupra cel putin unui vecin
}

void discharge(int u) {
  int v;

  while (excess[u] > 0) // avem ce trimite
    if (seen[u] < n) {  // continuam cu vecinul la care am ramas
      v = seen[u] + 1;    // varfurile sunt numerotate de la 1
      if ((C[u][v] - F[u][v] > 0) and (height[u] > height[v])) // se poate trimite apa din u in v
        push(u, v);
      else
        seen[u]++;
    }
    else { // we have checked all neighbours. must relabel
      relabel(u);
      seen[u] = 0; // data viitoare vor fi verificati toti vecinii
    }
}

void init () {
  ifstream fi("maxflow.in");
  int i, v1, v2, aux;
  Nod* c;

  fi >> n >> m; // noduri, muchii
  for (i = 1; i <= m; i++) {
    fi >> v1 >> v2 >> aux; // capacitatile arcelor [! trebuie aux ! altfel nu citeste bine datorita alocarii cu huge]
    C[v1][v2] = aux;
  }
  for (i = 2; i <= n; i++) {
    height[i] = excess[i] = 0;
    seen[i] = 0;
  }
  height[1] = n; // longest path from source to sink is less than n long
  excess[1] = INT_MAX; // initial avem la dispozitie oricata apa in sursa
  s1 = new Nod; s2 = new Nod; // lista nodurilor diferite de sursa si destinatie
  s1->urm = s2; s2->pred = s1;// lista vida
  for (i = 2; i <= n-1; i++) {
    c = new Nod; // adaugam nodurile pe rand, in fatza santinelei 2
    c->n = i; c->pred = s2->pred; c->urm = s2;
    s2->pred->urm = c; s2->pred = c;
  }
}

int result () {
  int s = 0;
  for (int v = 1; v <= n; v++)
    s += F[1][v];
/*
  for (int v1 = 1; v1 <= n; v1++)
    for (int v2 = 1; v2 <= n; v2++)
      if (C[v1][v2])
        fout << v1 << ' ' << v2 << ' ' << F[v1][v2] << endl;
*/
  return s;
}

int main () {
  int v, old_height, aux;
  Nod* c;
  Nod* p;

  init ();
  for (v = 2; v <= n-1; v++) // send as much flow as possible to neighbours of source
    push(1, v);
  c = s1->urm; // nodul curent
  while (c != s2) {
    v = c->n;
    old_height = height[v];
    discharge(v); // Este posibil ca height[v] sa se modifice.
    if (height[v] > old_height) { // move to front of list
      aux = c->n;
      c->pred->urm = c->urm; c->urm->pred = c->pred; // scoatem din lista nodul curent
      delete c;
      p = new Nod;
      p->n = aux; p->urm = s1->urm; p->pred = s1; // punem valoarea la inceputul listei
      s1->urm->pred = p; s1->urm = p;
      c = s1->urm;                    // restart from front
    }
    else
      c = c->urm;
  }
  fout << result();
  //getch();
}