#include <stdio.h>
#include <vector>
#include <queue>

/*
 * Input
N M <nr nodes/ nr muchii>
[M lines] x y z < muchie x -> y cu capacitatea z >
 */

#define MAX_NODES 1010
#define MAX_EDGES 5010

#define OUT    1
#define IN     2
#define NONE   0

FILE *FI = fopen("maxflow.in","r");
FILE *FO = fopen("maxflow.out","w");

struct Edge
{
	int s, d, flow, cap;
	int getNei(int n)
		{
			if(s==n)
				return d;
			if(d==n)
				return s;
			return 0;
		}
	int getDir(int n)
		{
			if(s==n)
				return OUT;
			if(d==n)
				return IN;
			return NONE;
		}

	// void print()
	// 	{
	// 		printf("%i -> %i [%i/%i]\n", s, d, flow, cap);
	// 	}
} edges[MAX_EDGES];

struct Node
{
	int label, overflow, id, present;
	std::vector <Edge *> nei;

	// void print()
	// 	{
	// 		printf("%i - %i %i\n", id, label, overflow);
	// 	}
} nodes[MAX_NODES];

class Comp
{
public:
	bool operator() (Node *a, Node *b)
{
	if(a->label < b->label)
		return true;
	if(a->label == b->label && a->overflow < b->overflow)
		return true;
	return false;
}
};

std::priority_queue <Node *, std::vector<Node *>, Comp > q;
int N,M;

inline int min(int a, int b) { if(a<b) return a; return b; }
void relabel(Node *n);
void push(Node *n)
{
	for(Edge *e : n->nei)
	{
		int nei = e->getNei(n->id);
		int dir = e->getDir(n->id);
		int dif;

		if(nodes[nei].label < n->label)
		switch(dir)
		{
		case OUT:
			dif = min(n->overflow, e->cap - e->flow);
			nodes[nei].overflow += dif;
			n->overflow -= dif;
			e->flow += dif;
			if(nodes[nei].present == false && nei != N)
			{
				q.push(&nodes[nei]);
				nodes[nei].present = true;
			}
			break;

		case IN:
			dif = min(n->overflow, e->flow);
			nodes[nei].overflow += dif;
			n->overflow -= dif;
			e->flow -= dif;
			if(nodes[nei].present == false && nei != N)
			{
				q.push(&nodes[nei]);
				nodes[nei].present = true;
			}
			break;
		}
	}

	if(n->overflow)
		relabel(n);
}

void relabel(Node *n)
{
	int minl = 0x0fffffff;
	for(Edge *e : n->nei)
	{
		int nei = e->getNei(n->id);
		int dir = e->getDir(n->id);
		
		switch(dir)
		{
		case OUT:
			if(e->flow < e->cap)
				minl = min(minl, nodes[nei].label+1);
			break;
		case IN:
			if(e->flow > 0)
				minl = min(minl, nodes[nei].label+1);
			break;
		}
	}

	n->label = minl;
	push(n);
}

int main()
{
	int x, y, z, i;
	fscanf(FI, "%i%i", &N, &M);

	for(i=0; i<M; ++i)
	{
		fscanf(FI, "%i%i%i", &x, &y, &z);
		edges[i].s = x;
		edges[i].d = y;
		edges[i].cap = z;
		nodes[x].nei.push_back(&edges[i]);
		nodes[y].nei.push_back(&edges[i]);
	}

	for(i=1; i<=N; ++i)
		nodes[i].id=i;

	for( Edge *e : nodes[1].nei)
	{
		int nei;
		if(e->s != 1)
			continue;

		nei = e->d;
		nodes[nei].overflow = e->cap;
		e->flow = e->cap;
		nodes[nei].present = true;
		q.push(&nodes[nei]);
	}
	nodes[1].label = N;

	while(!q.empty())
	{
		Node *n = q.top();
		q.pop();
		n->present = false;
		push(n);
	}

	fprintf(FO, "%i\n", nodes[N].overflow);
	return 0;
}