#ifndef _ALGORITHM_H
#define _ALGORITHM_H
#include <iostream>
using namespace std;

/**
	Algorithm abstract class
	specifies protocol
*/
class Algorithm
{
	/**
		read method
		reads input
	*/
	virtual void Read(istream &) = 0;

	/**
		solve method
		solves problem
	*/
	virtual void Solve() = 0;

	/**
		write method
		writes output
	*/
	virtual void Write(ostream &) = 0;
};

#endif

#ifndef _MAXFLOW_H
#define _MAXFLOW_H

#include "algorithm.h"
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

/**
	MaxFlow class
	solves the maximum flow in a network problem
*/
class MaxFlow: public Algorithm
{
	int N, K, A;
	queue<int> Q;
	vector< vector<int> > Deg, Cap, Flw;
	vector<int> Vis, Ftr;

public:

	/**
		maxflow method
		runs algorithm
	*/
	MaxFlow(istream &, ostream &);

private:

	/**
		read method
		reads input
	*/
	void Read(istream &);

	/**
		solve method
		solves problem
	*/
	void Solve();

	/**
		write method
		writes output
	*/
	void Write(ostream &);

	/**
		flow method
		computes flow
	*/
	int Flow();
};

#endif

#include "maxflow.h"

/**
	maxflow method
	runs algorithm
*/
MaxFlow::MaxFlow(istream &in, ostream &out):K(0), A(0)
{
	Read(in);
	Solve();
	Write(out);
}

/**
	read method
	reads input
*/
void MaxFlow::Read(istream &in)
{
	int x, y, c, m;
	vector<int> Aux1, Aux2;

	in >> N >> m;
	Aux2.assign(N + 1, 0);

	for (c = 0; c <= N; ++c)
	{
		Deg.push_back(Aux1);
		Cap.push_back(Aux2);
		Flw.push_back(Aux2);
	}

	while (m--)
	{
		in >> x >> y >> c;
		Cap[x][y] = c;
		Deg[x].push_back(y);
		Deg[y].push_back(x);
	}
}

/**
	flow method
	computes flow
*/
int MaxFlow::Flow()
{
	Q.push(1);
	Vis[1] = ++K;

	while (!Q.empty())
	{
		int u = Q.front();

		for (vector<int>::iterator i = Deg[u].begin(); i != Deg[u].end(); ++i)
		{
			int v = *i;

			if (Vis[v] < K)
			{
				if (Cap[u][v] > Flw[u][v])
				{
					Vis[v] = K;
					Ftr[v] = u;

					if (v < N)
						Q.push(v);
				}
			}
		}

		Q.pop();
	}

	if (Vis[N] < K)
	{
		return 0;
	}

	int a = 0;

	for (vector<int>::iterator i = Deg[N].begin(); i != Deg[N].end(); ++i)
	{
		int n = *i;

		if (Vis[n] == K && Cap[n][N] > Flw[n][N])
		{
			int f = Cap[n][N] - Flw[n][N], v;
			
			for (v = n; v > 1 && f > 0; v = Ftr[v])
			{
				int u = Ftr[v];
				f = min(f, Cap[u][v] - Flw[u][v]);
			}

			if (f > 0)
			{
				for (Ftr[N] = n, v = N; v > 1; v = Ftr[v])
				{
					int u = Ftr[v];
					Flw[u][v] += f;
					Flw[v][u] -= f;
				}

				a += f;
			}
		}
	}
	
	return a;
}

/**
	solve method
	solves problem
*/
void MaxFlow::Solve()
{
	int a;

	Vis.assign(N + 1, 0);
	Ftr.assign(N + 1, 0);

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

/**
	write method
	writes output
*/
void MaxFlow::Write(ostream &out)
{
	out << A;
}









int main()
{
	ifstream fin("maxflow.in");
	ofstream fout("maxflow.out");
	MaxFlow flow(fin, fout);

	fin.close();
	fout.close();
	return 0;
}