#include <fstream>
#include <iostream>
#include <queue>
#define MAX 1001
#define INFINITY 0x3fffffff
#define min(x, y) (x>y?y:x)

using std::ifstream;
using std::ofstream;
using std::queue;

int f[MAX][MAX], c[MAX][MAX], n, source, sink;
int visited[MAX];

void read()
{
	int a, b, cost, m;
	ifstream fin("maxflow.in");
	fin>>n>>m;
	
	while(m--)
	{
		fin>>a>>b>>cost;
		c[a][b]=cost;
	}
	source = 1;
	sink = n;
	fin.close();	
}

int breadth_first() //returns 1 if the sink can't be marked
{
	queue<int> nodes;
	int current;

	nodes.push(source);
	visited[source] = 1;

	while(!nodes.empty() && !visited[sink]) //standard breadth first
	{
		current = nodes.front();
		for(int i=1; i<=n; ++i)
			if(!visited[i])
				if(f[current][i] < c[current][i]) //we have positive flow
				{
					visited[i] = current;
					nodes.push(i);
				}
				else if (f[i][current] > 0)
				{
					visited[i]= -current;
					nodes.push(i);
				}
		nodes.pop();
	}
	return !visited[sink];
}

void max_flow()
{
	int path[MAX], last, a_min, b_min, e_flow;
	
	
	while(1)
	{
		memset(visited, 0, sizeof(visited));
		if(breadth_first())
			return;

		path[0] = sink;
		last = 0;

		a_min = INFINITY;
		b_min = INFINITY;

		while(path[last] != source)
		{
			++last;
			path[last] = abs(visited[path[last-1]]);
			
			if(visited[path[last-1]] > 0)
				a_min = min(a_min, c[path[last]][path[last-1]] - f[path[last]][path[last-1]]);
			else if (visited[path[last-1]] < 0)
				b_min = min(b_min, f[path[last]][path[last-1]]);
		}

		e_flow = min(a_min, b_min);

		for(int i = last; i>0; --i)
			if(visited[path[i-1]]>0)
				f[path[i]][path[i-1]] += e_flow;
			else
				f[path[i]][path[i-1]] -= e_flow;
	}
}

void show()
{
	ofstream fout("maxflow.out");

	int max_flow = 0;
	for(int i = 1; i <= n; ++i)
		max_flow += f[i][sink];
	fout<<max_flow<<"\n";
	
	fout.close();
}


int main ()
{
	read();
	max_flow();
	show();
}