#define MAX_N 1000
#define MAX_M 5000
#define INF 0x3f3f3f3f
 
#include <iostream>
 
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
using namespace std;
 
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
 
struct edge
{
	int u, v, flow, capacity, id;
	edge* reverse;
};
 
struct edgestacknode
{
	edgestacknode(edge* _e) :
		e(_e)
	{
	}
	
	edge* e;
	edgestacknode* prev = nullptr;
};
 
struct edgestack
{	
	~edgestack()
	{
		while (!Empty())
		{
			Pop();
		}
	}
	
	edgestacknode* top = nullptr;
	
	void Push(edgestacknode* node)
	{
		edgestacknode* prev = top;
		top                 = node;
		top->prev           = prev;
	}
	
	void Pop()
	{
		edgestacknode* prev = top->prev;
		delete top;
		top = prev;
	}
	
	bool Empty() const
	{
		return top == nullptr;
	}
};
 
int n, m, maxFlow, L[MAX_N + 1];
vector<edge*> G[MAX_N + 1];

int edgeId;
bitset<(MAX_M * 2) + 1> E;
 
void Read();
bool Bfs();
pair<bool, int> Augment(int node, int mi);
 
int main()
{
	Read();
	
	E.set();
	while (Bfs())
	{
		Augment(1, INF);
	}
	
	// Cleanup.
	for (int i = 1; i <= n; ++i)
	{
		for (edge* ptr : G[i])
		{
			delete ptr;
		}
		G[i].clear();
	}
	
	fout << maxFlow;
	
	fin.close();
	fout.close();
	return 0;
}
 
void Read()
{
	fin >> n >> m;
	
	for (int i = 0, x, y, c; i < m; ++i)
	{
		fin >> x >> y >> c;
		
		edge* a     = new edge;
		a->u        = x;
		a->v        = y;
		a->flow     = 0;
		a->capacity = c;
		a->id       = ++edgeId;
		
		edge* b 	= new edge;
		b->u		= y;
		b->v		= x;
		b->flow		= 0;
		b->capacity = 0;
		b->id       = ++edgeId;
		
		a->reverse = b;
		b->reverse = a;
		
		G[x].push_back(a);
		G[y].push_back(b);
	}
}
 
bool Bfs()
{
	for (int i = 1; i <= n; ++i)
	{
		L[i] = INF;
	}
	
	queue<int> Q;
	Q.push(1);
	L[1] = 1;
	
	while (!Q.empty())
	{
		int curr = Q.front();
		Q.pop();
		
		for (edge* e : G[curr])
		{
			if (E[e->id] && (L[e->v] > (L[curr] + 1)) && (e->capacity > e->flow))
			{
				L[e->v] = L[curr] + 1;
				Q.push(e->v);
			}
		}
	}
	
	return (L[n] != INF);
}
 
edgestack path;
pair<bool, int> Augment(int node, int mi)
{	
	if (node == n)
	{
		int mi_new = mi;
		for (edgestacknode* it = path.top; it != nullptr; it = it->prev)
		{
			it->e->flow          += mi;
			it->e->reverse->flow -= mi;
			
			mi_new = min(mi_new, it->e->capacity - it->e->flow);
		}
		
		maxFlow += mi;
		
		return { true, mi_new };
	}
	
	bool res = false;
	for (edge* e : G[node])
	{	
		if (E[e->id] && (L[e->v] == (L[node] + 1)) && (e->capacity > e->flow))
		{
			path.Push(new edgestacknode(e));
			pair<bool, int> res_neigh = Augment(e->v, min(mi, e->capacity - e->flow));
			path.Pop();
			
			if (!res_neigh.first)
			{
				E[e->id] = false;
			}
			else
			{
				mi = res_neigh.second;
				res = true;
			}
		}
	}
	
	return { res, mi };
}