#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
const int NMAX = 1001;
const int INF = 1000000010;
using namespace std;

int N, M;
int c[NMAX][NMAX];
int f[NMAX][NMAX];
vector<int> G[NMAX];
vector<bool> viz;
pair<int, int> much;
int tata[NMAX];
int flux = 0;
vector<bool> viz1;
vector<bool> viz2;

void citire()
{
	cin >> N >> M;
	int x, y, cap;
	for(int i = 1 ; i <= M ; i++)
	{
		cin >> x >> y >> cap;
		G[x].push_back(y);
		G[y].push_back(x);
		c[x][y] = cap;
		c[y][x] = cap;
		much.push_back(make_pair(x, y));
	}
}

inline bool BFS()
{
	fill(viz.begin(), viz.end(), false);
	queue<int> Q;
	Q.push(1);
	int x;
	vector<int> :: iterator it;
	
	while(!Q.empty())
	{
		x = Q.front();
		Q.pop();
		if(x != N)
			for(it = G[x].begin() ; it != G[x].end() ; it++)
				if(!viz[*it] && c[x][*it] > f[x][*it])
				{
					tata[*it] = x;
					viz[*it] = true;
					Q.push(*it);
				}
	}
	
	return viz[N];
}

void FLUX()
{
	viz.resize(N);
	vector<int> :: iterator it;
	while(BFS())
		for(it = G[N].begin() ; it != G[N].end() ; it++)
			if(!viz[*it] && c[N][*it] > f[N][*it])
			{
				int minim = INF;
				tata[N] = *it;
				for(int i = N ; i != 1; i = tata[i])
					minim = min(minim, c[tata[i]][i] - f[tata[i]][i]);
				if(minim < 0 )
					break;
				flux+= minim;
				for(int i = N ; i != 1 ; i = tata[i])
				{
					f[tata[i]][i] += flux;
					f[i][tata[i]] -= flux;
				}
			}
}

void dfs1()
{
}

int main()
{
	freopen("critice.in","r",stdin);
	freopen("critice.out","w",stdout);
	citire();
	FLUX();
	viz1.resize(N);
	dfs1();
	dfs2();
	scrie();
	return 0;
}