#include <fstream>
#include <climits>
//#include <conio>

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; // se lucreaza cu al doilea element din lista, primul are rezervorul gol
	}
	fout << result();
  //getch();
}