#include <fstream>
#include <queue>
#include <vector>
#define nmax 1024

using namespace std;

int N, M, A, K, I;
queue<int> Q;
vector<int> G[nmax];
int C[nmax][nmax], F[nmax][nmax];
vector<int> Vis, Father, Flow;

void read()
{
	int x, y, c;

	ifstream fin("maxflow.in");
	fin >> N >> M;
	
	for (int i = 0; i < M; ++i)
	{
		fin >> x >> y >> c;
		C[x][y] = c;
		G[x].push_back(y);
		G[y].push_back(x);

		if (x == 1 || y == 1)
			I += c;
	}
	
	fin.close();
}

void clear()
{
   std::queue<int> R;
   std::swap(Q, R);
}

int flow()
{
	clear();
	Q.push(1);
	Flow[1] = I;
	Flow[N] = 0;
	Vis[1] = ++K;

	while (!Q.empty() && Vis[N] < K)
	{
		int u = Q.front();

		for (vector<int>::iterator i = G[u].begin(); i != G[u].end() && Vis[N] < K; ++i)
		{
			int v = *i;

			if (Vis[v] < K)
			{
				if (C[u][v] - F[u][v] > 0)
				{
					Vis[v] = K;
					Father[v] = u;
					Flow[v] = min(Flow[u], C[u][v] - F[u][v]);
					Q.push(v);
				}
			}
		}

		Q.pop();
	}

	for (int v = N; v > 1; v = Father[v])
	{
		int u = Father[v];
		F[u][v] += Flow[N];
		F[v][u] -= Flow[N];
	}
	
	return Flow[N];
}

void solve()
{
	Vis.assign(N + 1, 0);
	Father.assign(N + 1, 0);
	Flow.assign(N + 1, 0);

	int a;

	while (a = flow())
		A += a;
}

void write()
{
	ofstream fout("maxflow.out");
	fout << A << '\n';
	fout.close();
}

int main()
{
	read();
	solve();
	write();
	return 0;
}