#include <stdio.h>
#include <iostream>

using namespace std;

#define MAX_N 1001
#define NIL -1
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))
#define MAX(X, Y) (((X) > (Y)) ? (X) : (Y))

int c[MAX_N][MAX_N]; // matrice de adiacență
int sv[MAX_N];      // sv[u] = vecinul curent din vecinii lui u
int e[MAX_N];        // excesul
int h[MAX_N];        // înălțimea
int hc[2 * MAX_N];   // hc[i] = numărul de noduri de înălțime i
int urm[MAX_N], ant[MAX_N]; // sortare topologică a rețelei admisibile
int head;            // începutul listei urm-ant
int n, m;

void initPreflow() {
  h[1] = n;
  hc[0] = n - 1;
  hc[n] = 1;
  for (int u = 1; u <= n; u++) {
    int vol = c[1][u];
    e[1] -= vol;
    e[u] = vol;
    c[1][u] = 0;
    c[u][1] += vol;
    sv[u] = 1;
  }
  for (int i = 2; i < n - 1; i++) {
    urm[i] = i + 1;
    ant[i + 1] = i;
  }
  ant[2] = NIL;
  urm[n - 1] = NIL;
  head = 2;
}

void push (int u, int v) {
  int vol = MIN(e[u], c[u][v]);
  e[u] -= vol;
  cout << u << ' ' << e[u] << ' ';
  e[v] += vol;
  cout << v << ' ' << e[v] << '\n' ;
  c[u][v] -= vol;
  c[v][u] += vol;
}

void relabel (int u) {
  int oldh = h[u];
  hc[h[u]]--;
  h[u] = 2 * n; // căci înălțimile nu vor depăși 2n - 1
  for (int v = 1; v <= n; v++) {
    if (c[u][v]) {
      h[u] = MIN(h[u], 1 + h[v]);
    }
  }
  hc[h[u]]++;

  // gap heuristic
  /*
  if (!hc[oldh]) {
    for (int v = 0; v < n; v++) {
      if (h[v] > oldh) {
        h[v] = MAX(h[v], n + 1);
      }
    }
  }
  */
}

// Returnează 1 dacă a făcut vreo operație relabel
void discharge (int u) {
  int oldh = h[u];
  while (e[u]) {
    if (c[u][sv[u]] && (h[u] == h[sv[u]] + 1)) {
      push(u, sv[u]);
    }
    sv[u]++;
    if (sv[u] == n + 1) {
      sv[u] = 1;
      relabel(u);
    }
  }
}

int main(void) {
  FILE *f = fopen("maxflow.in", "r");
  int i, j;
  fscanf(f, "%d%d", &n, &m);
  for (int im = 1; im <= m; im++) {
    fscanf(f, "%d%d", &i, &j);
    fscanf(f, "%d", &c[i][j]);
  }
  fclose(f);
  initPreflow();
  int u = head;
  while (u != NIL) {
    if (e[u]) {
      relabel(u);
      discharge(u);
      if (ant[u] != NIL) { // altfel u este deja primul
        urm[ant[u]] = urm[u];
        if (urm[u] != NIL) {
          ant[urm[u]] = ant[u];
        }
        urm[u] = head;
        ant[u] = NIL;
        ant[head] = u;
        head = u;
      }
    }
    u = urm[u];
  }

  f = fopen("maxflow.out", "w");
  fprintf(f, "%d\n", e[n]);
  fclose(f);
}