#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
using namespace std;

// fisiere
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

// variabile
int n, m, sursa = 1,destinatie;
vector<vector<int>> lista_adiacenta;
vector<vector<int>> costuri;
vector<vector<int>> flux;
vector<vector<int>> lista_adiacenta_inversa;
vector<int> tata;
vector<int> viz;

void citire()
{
	fin >> n >> m;
	int a, b, c;
	destinatie = n;
	lista_adiacenta = vector<vector<int>>(n+1, vector<int>());
	lista_adiacenta_inversa = vector<vector<int>>(n + 1, vector<int>());
	costuri = vector<vector<int>>(n+1, vector<int>(n+1,0));
	flux = vector<vector<int>>(n + 1, vector<int>(n + 1, 0));
	for (int i = 0; i < n + 1; i++)
	{
		for (int j = 0; j < n + 1; j++)
		{
			costuri[i][j] = 0;
			flux[i][j] = 0;
		}
	}
	for (int i = 0; i < m; i++)
	{
		fin >> a >> b >> c;
		lista_adiacenta[a].push_back(b);
		lista_adiacenta_inversa[b].push_back(a);
		costuri[a][b] = c;
	}
}
bool construieste_lant()
{
	tata = vector<int>(n + 1, 0);
	viz = vector<int>(n + 1, 0);
	queue<int> coada;
	coada.push(sursa);
	viz[sursa] = 1;
	while (!coada.empty())
	{
		int nod = coada.front();
		coada.pop();
		for (auto j : lista_adiacenta[nod])
		{
			if (viz[j] == 0 && costuri[nod][j] - flux[nod][j] > 0)
			{
				coada.push(j);
				viz[j] = 1; tata[j] = nod;
			}
		}
		if (viz[destinatie] == 1)
			return true;
		for (auto j : lista_adiacenta_inversa[nod])
		{
			if (viz[j] == 0 && flux[j][nod] > 0)
			{
				coada.push(j);
				viz[j] = 1; tata[j] = -nod;
			}
		}
		if (viz[destinatie] == 1)
			return true;
	}
	return false;
}
int main()
{
	citire();
	int fluxmaxim = 0;
	while (construieste_lant() == true) 
	{
		int iP = 110001; //i(P)
		int t = destinatie;
		while (t != sursa) {
			if (tata[t] >= 0)
			{
				if (costuri[tata[t]][t] - flux[tata[t]][t] < iP)
					iP = costuri[tata[t]][t] - flux[tata[t]][t];
				t = tata[t];
			}
			else
			{
				if (flux[t][-tata[t]] < iP)
					iP = flux[t][-tata[t]];
				t = -tata[t];
			}

		}
		t = destinatie;
		while (t != sursa)
		{
			if (tata[t] >= 0)
			{
				flux[tata[t]][t] += iP;
				t = tata[t];
			}
			else
			{
				flux[t][-tata[t]] -= iP;
				t = -tata[t];
			}
		}
		fluxmaxim += iP;
	}
	fout << fluxmaxim;
}