#include <iostream>
#include <fstream>
#include <list> 


std::ifstream fin{ "maxflow.in" };
std::ofstream fout{ "maxflow.out" };


const int oo = int(1e9);

const int N_MAX = 1000 + 1;
const int M_NAX = 5000 + 1;


int N, M;

int s, t;

int capacity[N_MAX][N_MAX];
int preflow[N_MAX][N_MAX];

int excess[N_MAX];
int height[N_MAX];
int next[N_MAX];


std::list<int> L;


void relabel(int u)
{
	int min_height = oo;

	for (int v = 1; v <= N; ++v)
	{
		if (preflow[u][v] < capacity[u][v] && height[u] <= height[v])
		{
			min_height = std::min(min_height, height[v]);
		}
	}

	height[u] = min_height + 1;
}


void push(int u, int v)
{
	int delta = std::min(excess[u], capacity[u][v] - preflow[u][v]);

	preflow[u][v] += delta;
	preflow[v][u] -= delta;

	excess[u] -= delta;
	excess[v] += delta;
}


void discharge(int u)
{
	while (excess[u] > 0)
	{
		if (next[u] > N)
		{
			relabel(u);
			next[u] = 1;
		}
		
		if (preflow[u][next[u]] < capacity[u][next[u]] && height[u] == height[next[u]] + 1)
		{
			push(u, next[u]);
		}
		else
		{
			++next[u];
		}
		
	}
}


int main()
{
	fin >> N >> M;


	s = 1;
	excess[s] = oo;
	height[s] = N;

	t = N;


	for (int i = 1; i <= M; ++i)
	{
		int u, v, c;

		fin >> u >> v >> c;

		capacity[u][v] = c;

		if (s == u)
		{
			push(s, v);
		}
	}


	for (int u = 1; u <= N; ++u)
	{
		next[u] = 1;

		if (u != s && u != t)
		{
			L.push_back(u);
		}
	}


	auto it = L.begin();

	while (it != L.end())
	{
		int u = *it;
		int old_height = height[u];

		discharge(u);

		if (old_height != height[u])
		{
			L.erase(it);
			L.push_front(u);
			it = L.begin();
		}

		++it;
	}


	fout << excess[t];
}