#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];



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;
}



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

		if (excess[u] > 0)
			return u;
	}
		

	return -1;
}



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);
		}
	}


	int u = get_excess_node();

	while (u != -1)
	{
		bool pushed = false;

		for (int v = 1; v <= N; ++v)
		{
			if (height[u] == height[v] + 1 && preflow[u][v] < capacity[u][v])
			{
				push(u, v);

				pushed = true;
				break;
			}
		}

		if (pushed == false)
		{
			relabel(u);
		}

		u = get_excess_node();
	}

	fout << excess[t] << '\n';
}