#include <fstream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

fstream fin("maxflow.in", ios::in);
fstream fout("maxflow.out", ios::out);

#define s second
#define f first
#define MAXN 1005
pair<int, int> NT[MAXN][MAXN], p[MAXN];
vector <int> ways;
int N, M, used[MAXN], flow;

inline void read()
{
	fin >> N >> M;
	for (int i = 1, x, y, c; i <= M; i++){
		fin >> x >> y >> c;
		NT[x][y].s = c;
		if (y == N) ways.push_back(x);
	}
	fin.close();
}
void BFS()
{
	used[N] = 1;
	memset(used + 2, 0, sizeof(int) * N);
	queue <int> q;
	q.push(1);

	while (!q.empty()){
		int node = q.front();
		q.pop();
		if (node == N) continue;

		for (int i = 1, m_flow; i <= N; i++){
			m_flow = NT[node][i].s - NT[node][i].f;
			if (!used[i] && (m_flow > 0 || NT[i][node].first))
				q.push(i),
				used[i] = 1,
				p[i].f = node,
				p[i].s = !m_flow ? false : true;
		}
	}
}

int main()
{
	read();
	used[1] = 1;

	while (true){
		BFS();
		if (!used[N]) break;
		int m_flow;

		for (int i = 0, node; i < (int)ways.size(); i++){
			p[N].f = ways[i];
			for (node = N, m_flow = ~(1 << 31); node != 1; node = p[node].f)
				m_flow = min(m_flow, p[node].s ? NT[p[node].f][node].s - NT[p[node].f][node].f
											   : NT[node][p[node].f].f);
			if (!m_flow) continue;
			for (node = N; node != 1; node = p[node].f)
				p[node].s ? NT[p[node].f][node].f += m_flow : NT[p[node].f][node].f -= m_flow;
			flow += m_flow;
		}
	}
	fout << flow << "\n";

	fout.close();
	return 0;
}