#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
using namespace std;
const int NMAX = 1001;
const int MMAX = 5001;
const int INF = 1000000000;
int N, M;
vector<int> V[NMAX];
vector<int> tata;
int c[NMAX][NMAX];
int f[NMAX][NMAX];
int flux = 0;

void citeste()
{
	int x, y, cost;
	scanf("%d%d",&N,&M);
	for(int i = 1 ; i <= M ; i++)
	{
		scanf("%d%d%d",&x,&y,&cost);
		V[x].push_back(y);
		V[y].push_back(x);
		c[x][y] = cost;
	}
}

int bfs()
{
	vector<bool> viz(NMAX, false);
	queue<int> Q;
	int nod;
	vector<int> :: iterator it;
	tata.resize(N);
	
	Q.push(1);
	viz[1] = 1;
	
	while(!Q.empty())
	{
		nod = Q.front();
		Q.pop();
		for(it = V[nod].begin() ; it != V[nod].end() ; it++)
			if(!viz[*it] && c[nod][*it] > f[nod][*it])
			{
				Q.push(*it);
				tata[*it] = nod;
				viz[*it] = 1;
			}
	}
	
	return viz[N];
}

void rezolva()
{
	vector<int> :: iterator it;
	while(bfs())
		for(it = V[N].begin() ; it != V[N].end() ; ++it)
		{
			tata[N] = *it;
			
			int minim = INF;
			for(int nod = N ; nod > 1 ; nod = tata[nod])
				minim = min(minim, c[tata[nod]][nod] - f[tata[nod]][nod]);
			
			if(minim == 0)
				continue;
			
			flux += minim;
			for(int nod = N ; nod > 1 ; nod = tata[nod])
				f[tata[nod]][nod] += minim;
		}
}

int main()
{
	freopen("maxflow.in","r",stdin);
	freopen("maxflow.out","w",stdout);
	citeste();
	rezolva();
	printf("%d\n",flux);
	return 0;
	
}