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

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;

struct Edge {
	int capacity{ 0 };
	int preflow{ 0 };
	bool exists{ false };
};

int N, M;
Edge graph[N_MAX][N_MAX];

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


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

	for (int v = 1; v <= N; ++v)
	{
		if (graph[u][v].preflow < graph[u][v].capacity && 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], graph[u][v].capacity - graph[u][v].preflow);

	graph[u][v].preflow += delta;
	graph[v][u].preflow -= 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 (graph[u][next[u]].preflow < graph[u][next[u]].capacity && height[u] == height[next[u]] + 1)
		{
			push(u, next[u]);
		}
		else
		{
			++next[u];
		}
		
	}
}


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

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

		fin >> u >> v >> c;

		graph[u][v].capacity = c;

		graph[u][v].exists = true;
		graph[v][u].exists = true;
	}

	int s = 1, t = N;


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

	for (int u = 1; u <= N; ++u)
	{
		if (graph[s][u].exists == true)
		{
			push(s, u);
		}

		next[u] = 1;
	}


	std::list<int> L;

	for (int u = 1; u <= N; ++u)
	{
		if (u == s || u == t) continue;

		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] << std::endl;
}