#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 360;
const int inf = (1 << 27);

int n, m, s, d;
int flux[N][N];
int capacitate[N][N];
int cost[N][N];
int oldDist[N];
int dist[N];
vector<int> vecini[N];
int sol = 0;
int solx = 0;
int tata[N];

void citire()
{
	scanf("%d %d", &n, &m);

	s = 0;
	d = n - 1;
		
	int tmp1, tmp2, tmp3;

	for(int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &tmp1, &tmp2, &tmp3);

		tmp1--;
		tmp2--;

		vecini[tmp1].push_back(tmp2);
		vecini[tmp2].push_back(tmp1);
		capacitate[tmp1][tmp2] = tmp3;
		cost[tmp1][tmp2] = 0;
		cost[tmp2][tmp1] = 0;
	}
}

void bellmanFord()
{
	queue<int> Q;

	Q.push(s);
	oldDist[s] = 0;

	while(Q.empty() == false)
	{
		int x = Q.front();
		int l = vecini[x].size();

		Q.pop();

		for(int i = 0; i < l; i++)
		{
			if(oldDist[vecini[x][i]] > oldDist[x] + cost[x][vecini[x][i]] && flux[x][vecini[x][i]] < capacitate[x][vecini[x][i]])	
			{
				oldDist[vecini[x][i]] = oldDist[x] + cost[x][vecini[x][i]];
				Q.push(vecini[x][i]);
			}
		}
	}
}

bool dijkstra()
{
	for(int i = 0; i < n; i++)
	{
		dist[i] = inf;
	}

	priority_queue<pair<int, int> > Q;	

	Q.push(make_pair(0, s));
	tata[s] = s;
	dist[s] = 0;

	while(Q.empty() == false)
	{
		int x = Q.top().second;
		int y = Q.top().first;

		Q.pop();

		if(dist[x] != y)
		{
			continue;
		}

		int l = vecini[x].size();

		for(int i = 0; i < l; i++)
		{
			if(flux[x][vecini[x][i]] < capacitate[x][vecini[x][i]])				
			{
				int z = cost[x][vecini[x][i]] + oldDist[x] - oldDist[vecini[x][i]];

				if(flux[x][vecini[x][i]] < capacitate[x][vecini[x][i]] && dist[vecini[x][i]] > dist[x] + z)
				{
					dist[vecini[x][i]] = dist[x] + z;
					tata[vecini[x][i]] = x;
					Q.push(make_pair(dist[vecini[x][i]], vecini[x][i]));
				}
			}
		}
	}

	if(dist[d] != inf)
	{
		return true;
	}

	return false;
}

void solve()
{
	while(dijkstra() == true)
	{
		int x = d;
		tata[s] = s;
		int valMin = inf;

		while(x != tata[x])
		{
			valMin = min(valMin, capacitate[tata[x]][x] - flux[tata[x]][x]);
			x = tata[x];
		}
		
		x = d;

		if(valMin == 0)
		{
			return;
		}

		while(x != tata[x])
		{
			flux[tata[x]][x] += valMin;
			solx += cost[tata[x]][x] * valMin;
			x = tata[x];
		}

		sol += valMin;
	}
}

void afisare()
{
	printf("%d", sol);
}

int main()
{
	freopen("maxflow.in", "r", stdin);
	freopen("maxflow.out", "w", stdout);

	citire();
	bellmanFord();
	solve();
	afisare();

	return 0;
}