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

using namespace std;

#define NUMAR_MAXIM_DE_MUCHII 5001
#define NUMAR_MAXIM_DE_NODURI 1001
#define oo 1<<30

int n, m;

int a[NUMAR_MAXIM_DE_NODURI][NUMAR_MAXIM_DE_NODURI]; //liste de adiacenta
int c[NUMAR_MAXIM_DE_NODURI][NUMAR_MAXIM_DE_NODURI]; //capacitati pentru arce
int f[NUMAR_MAXIM_DE_NODURI][NUMAR_MAXIM_DE_NODURI]; //flux
int pred[NUMAR_MAXIM_DE_NODURI];
int viz[NUMAR_MAXIM_DE_NODURI];

long max_flow = 0; //flux maxim, initial 0

queue<int> q;

inline int min(int a, int b)
{
	if( a > b ) return b;
	return a;
}

void citeste()
{
	//citeste datele de intrare
	
	int i;
	
	FILE* fi = fopen("maxflow.in", "r");
	fscanf(fi, "%d %d\n", &n, &m);
	
	//cream matricea de adiacenta
	int x, y, capacitate;
	
	for(i = 0; i < m; ++i)
	{
		fscanf(fi, "%d%d%d", &x, &y, &capacitate);
		
		if(c[x][y] == 0) 
		{
			a[x][++a[x][0]] = y;
			a[y][++a[y][0]] = x;
		}
		c[x][y] += capacitate;
	}
	
	fclose(fi);
}

void scrie()
{
	FILE* fo = fopen("maxflow.out", "w");
	fprintf(fo, "%ld\n", max_flow);
	fclose(fo);
}

int bfs()
{	
	int e, i, v;

	memset(pred, 0, sizeof(pred));
	memset(viz, 0, sizeof(viz));
	
	//while(q.size() > 0) q.pop();
	q.push(1); //introducem in coada sursa retelei de transport
	
	viz[1] = 1;

	
	while(!q.empty())
	{
		e = q.front();
		q.pop();
		
		for(i = 1; i <= a[e][0]; ++i)
		{
			v = a[e][i];
			if((!viz[v]) && (c[e][v] - f[e][v] > 0))
			{
				viz[v] = 1;
				pred[v] = e;
				if(v == n) continue;
				q.push(v);
			}			
		}
	}
	
	return viz[n];
}

void ford_fulkerson()
{
	int inc, u, i, nod;
	max_flow = 0;
 	while(bfs())
	{
		for(i = 1; i <= a[n][0]; ++i)
		{
			nod = a[n][i];
			
			if(f[nod][n] == c[nod][n] || !viz[nod]) continue;
			
			pred[n] = nod;
			
			inc = oo;
		
			for(u = n; pred[u] > 0; u = pred[u]) inc = min(inc, c[pred[u]][u] - f[pred[u]][u]);
			for(u = n; pred[u] > 0; u = pred[u])
			{
				f[pred[u]][u] += inc;
				f[u][pred[u]] -= inc;
			}
			
			max_flow += inc;
//			printf("%d\n", max_flow);
		}
	}
}

int main()
{
	citeste();
	ford_fulkerson();
	scrie();
	return 0;
}