#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <limits>
#include <vector>
#include <queue>
#include <ctime>
#include <list>

using namespace std;


// Net class:

template <class Edge>
class Net {
	private:
		typedef Edge* EdgePointer;
		vector<EdgePointer> edges;
		vector<list<EdgePointer> > outerEdges;
		vector<list<EdgePointer> > innerEdges;

		// ХОЧЕТСЯ iter.begin(), iter.end(), iter ++, iter --, =, ==, (bool)
		class UniversalEdgeIterator {
			friend class Net;

			private:
				bool undefined = true;
				list<Edge*> *edgeList;
				typename list<Edge*>::iterator iter;
	
				void set (list<Edge*> *edgeList) {
					this->edgeList = edgeList;
				}

				void validate () {
					if (undefined)
						setBegin();

					undefined = false;
				}

			public:
				void setBegin () {
					iter = edgeList->begin();
				}
	
				bool isEnd () const {
					return iter == edgeList->end() || edgeList->size() == 0;
				}

				void move () {
					validate();
					iter = next(iter);
				}

				Edge* get () {
					validate();
					return *iter;
				}
		};

		vector<UniversalEdgeIterator> outerEdgeIterator;
		vector<UniversalEdgeIterator> innerEdgeIterator;

	public:
		typedef UniversalEdgeIterator EdgeIterator;
		typedef typename Edge::IndexType IndexType;
		IndexType source;
		IndexType sink;

		Net (const IndexType &verticesCount) {
			outerEdges.resize(verticesCount);
			innerEdges.resize(verticesCount);
			innerEdgeIterator.resize(verticesCount);
			outerEdgeIterator.resize(verticesCount);

			for (unsigned i = 0; i < verticesCount; i ++) {
				innerEdgeIterator[i].set(&innerEdges[i]);
				outerEdgeIterator[i].set(&outerEdges[i]);
			}
		}

		~Net () {
			for (EdgePointer &edge: edges)
				delete edge;
		}

		void addEdge (const Edge &edge) {
			EdgePointer edgePointer = new Edge(edge);
			edges.push_back(edgePointer);
			outerEdges[edgePointer->from].push_back(edges.back());
			innerEdges[edgePointer->to].push_back(edges.back());

			EdgePointer reverseEdgePointer = new Edge(edge.getReverse());
			edges.push_back(reverseEdgePointer);
			outerEdges[reverseEdgePointer->from].push_back(edges.back());
			innerEdges[reverseEdgePointer->to].push_back(edges.back());

			edgePointer->reverseEdge = reverseEdgePointer;
			reverseEdgePointer->reverseEdge = edgePointer;
		}

		EdgeIterator& getInnerEdgeIterator (const IndexType &vertex) {
			return innerEdgeIterator[vertex];
		}

		EdgeIterator getConstInnerEdgeIterator (const IndexType &vertex) const {
			return innerEdgeIterator[vertex];
		}

		EdgeIterator& getOuterEdgeIterator (const IndexType &vertex) {
			return outerEdgeIterator[vertex];
		}

		EdgeIterator getConstOuterEdgeIterator (const IndexType &vertex) const {
			return outerEdgeIterator[vertex];
		}

		IndexType getVerticesCount () const {
			return outerEdges.size();
		}
};

template <class Edge>
void printNet (Net<Edge> &net, ostream &os = cout) {
	for (typename Edge::IndexType vertex = 0; vertex < net.getVerticesCount(); vertex ++) {
		typename Net<Edge>::EdgeIterator iter = net.getConstOuterEdgeIterator(vertex);

		for (iter.setBegin(); !iter.isEnd(); iter.move()) {
			iter.get()->print(cout);
			cout << " ";
		}

		cout << endl;
	}
}


// Global push-relabel-discharge algorithm:

template <class Edge>
void push (Net<Edge> &net, Edge *edge, vector<typename Edge::FlowType> &excess) {
	typename Edge::FlowType delta = min<typename Edge::FlowType>(excess[edge->from], edge->recidualCapacity());
	edge->flow += delta;
	edge->reverseEdge->flow -= delta;
	excess[edge->from] -= delta;
	excess[edge->to] += delta;
}

template <class Edge>
void relabel (const Net<Edge> &net, const typename Edge::IndexType &vertex, vector<typename Edge::IndexType> &height) {
	typename Edge::IndexType minHeight = numeric_limits<typename Edge::IndexType>::max();

	typename Net<Edge>::EdgeIterator iter = net.getConstOuterEdgeIterator(vertex);

	for (iter.setBegin(); !iter.isEnd(); iter.move()) {
		Edge *edge = iter.get();

		if (edge->recidualCapacity() > 0)
			minHeight = min<typename Edge::IndexType>(minHeight, height[edge->to]);
	}
	
	height[vertex] = minHeight + 1;
}

template <class Edge>
void discharge (Net<Edge> &net, const typename Edge::IndexType &vertex, vector<typename Edge::FlowType> &excess, vector<typename Edge::IndexType> &height) {
	cout << vertex << endl;
	while (excess[vertex] > 0) {
		typename Net<Edge>::EdgeIterator &iter = net.getOuterEdgeIterator(vertex);

		if (iter.isEnd()) {
			relabel(net, vertex, height);
			iter.setBegin();
		}

		else {
			Edge *edge = iter.get();

			if (edge->recidualCapacity() > 0 && height[vertex] == height[edge->to] + 1)
				push(net, edge, excess);

			else
				iter.move();
		}
	}
}

template <class Edge>
typename Edge::FlowType findMaxFlowWithPreflowPush (Net<Edge> &net) {
	vector<typename Edge::FlowType> excess(net.getVerticesCount(), 0);
	vector<typename Edge::IndexType> height(net.getVerticesCount(), 0);
	height[net.source] = net.getVerticesCount();

	typename Net<Edge>::EdgeIterator iter = net.getConstOuterEdgeIterator(net.source);

	for (iter.setBegin(); !iter.isEnd(); iter.move()) {
		Edge *edge = iter.get();

		edge->flow += edge->capacity;
		edge->reverseEdge->flow -= edge->capacity;

		if (edge->to != net.sink && edge->capacity > 0)
			excess[edge->to] += edge->capacity;
	}


	while (true) {
		bool discharged = false;

		for (typename Edge::IndexType vertex = 0; vertex < net.getVerticesCount(); vertex ++) {
			if (excess[vertex] && vertex != net.source && vertex != net.sink) {
				discharge(net, vertex, excess, height);
				discharged = true;
			}
		}

		if (!discharged)
			break;
	}


	typename Edge::FlowType maxFlow = 0;

	for (iter.setBegin(); !iter.isEnd(); iter.move())
		maxFlow += iter.get()->flow;
	
	return maxFlow;
}


// Dinic algorithm:

template <class Edge>
typename Edge::FlowType tryAugmentFlow (Net<Edge> &layeredNet, const typename Edge::IndexType &vertex, const typename Edge::FlowType &augmentation = numeric_limits<typename Edge::FlowType>::max()) {
	if (vertex == layeredNet.sink || augmentation == 0)
		return augmentation;
	
	for (typename Net<Edge>::EdgeIterator iter = layeredNet.getConstOuterEdgeIterator(vertex); !iter.isEnd(); iter.move()) {
		Edge *edge = iter.get();

		if (edge->capacity == 0)
			continue;

		typename Edge::FlowType newExcess = min<typename Edge::FlowType>(augmentation, edge->recidualCapacity());
		typename Edge::FlowType augmentedFlow = tryAugmentFlow(layeredNet, edge->to, newExcess);

		if (augmentedFlow != 0) {
			edge->flow += augmentedFlow;
			edge->reverseEdge->flow -= augmentedFlow;
			return augmentedFlow;
		}
	}

	layeredNet.getOuterEdgeIterator(vertex).move();
	return 0;
}

template <class Edge>
typename Edge::FlowType findBlockingFlowDinic (Net<Edge> &layeredNet) {
	typename Edge::FlowType blockingFlow = 0;

	while (true) {
		typename Edge::FlowType augmentedFlow = tryAugmentFlow(layeredNet, layeredNet.source);
		if (augmentedFlow == 0)
			break;
		
		else
			blockingFlow += augmentedFlow;
	}

	return blockingFlow;
}


// MKM:

template <class Edge>
typename Edge::FlowType countPotencial (const Net<Edge> &net, typename Net<Edge>::EdgeIterator iter) {
	typename Edge::FlowType potencial = 0;

	for (iter.setBegin(); !iter.isEnd(); iter.move())
		potencial += iter.get()->recidualCapacity();

	return potencial;
}

template <class Edge>
inline typename Edge::FlowType getPotencial (const Net<Edge> &net, const typename Edge::IndexType &vertex, const vector<typename Edge::FlowType> &innerPotencial, const vector<typename Edge::FlowType> &outerPotencial) {
	if (vertex == net.source)
		return outerPotencial[vertex];

	else if (vertex == net.sink)
		return innerPotencial[vertex];

	else
		return min<typename Edge::FlowType>(outerPotencial[vertex], innerPotencial[vertex]);
}

template <class Edge>
void deleteVertex (const Net<Edge> &layeredNet, const typename Edge::IndexType &vertex, vector<typename Edge::FlowType> &innerPotencial, vector<typename Edge::FlowType> &outerPotencial, vector<bool> &isDeleted) {
	if (isDeleted[vertex])
		return;

	isDeleted[vertex] = true;
	//cout << vertex << " ";


	typename Net<Edge>::EdgeIterator innerIter = layeredNet.getConstInnerEdgeIterator(vertex);

	for (innerIter.setBegin(); !innerIter.isEnd(); innerIter.move()) {
		Edge *edge = innerIter.get();

		if (edge->capacity == 0)
			continue;

		outerPotencial[edge->from] -= edge->recidualCapacity();

		if (getPotencial(layeredNet, edge->from, innerPotencial, outerPotencial) == 0)
			deleteVertex(layeredNet, edge->from, innerPotencial, outerPotencial, isDeleted);
	}


	typename Net<Edge>::EdgeIterator outerIter = layeredNet.getConstOuterEdgeIterator(vertex);

	for (outerIter.setBegin(); !outerIter.isEnd(); outerIter.move()) {
		Edge *edge = outerIter.get();

		if (edge->capacity == 0)
			continue;

		innerPotencial[edge->to] -= edge->recidualCapacity();

		if (getPotencial(layeredNet, edge->to, innerPotencial, outerPotencial) == 0)
			deleteVertex(layeredNet, edge->to, innerPotencial, outerPotencial, isDeleted);
	}
}

template <class Edge>
void pushFlowToSink (Net<Edge> &layeredNet, const typename Edge::IndexType &vertex, const typename Edge::FlowType &pushingFlow, vector<typename Edge::FlowType> &innerPotencial, vector<typename Edge::FlowType> &outerPotencial, const vector<bool> &isDeleted) {
	if (vertex == layeredNet.sink)
		return;

	typename Edge::FlowType excess = pushingFlow;
	
	for (typename Net<Edge>::EdgeIterator &iter = layeredNet.getOuterEdgeIterator(vertex); !iter.isEnd(); iter.move()) {
		Edge *edge = iter.get();

		if (edge->capacity == 0 || isDeleted[edge->to])
			continue;

		typename Edge::FlowType pushment = min<typename Edge::FlowType>(excess, edge->recidualCapacity());
		excess -= pushment;
		edge->flow += pushment;
		edge->reverseEdge->flow -= pushment;
		outerPotencial[edge->from] -= pushment;
		innerPotencial[edge->to] -= pushment;

		pushFlowToSink(layeredNet, edge->to, pushment, innerPotencial, outerPotencial, isDeleted);

		if (excess == 0)
			break;
	}
}

template <class Edge>
void pushFlowFromSource (Net<Edge> &layeredNet, const typename Edge::IndexType &vertex, const typename Edge::FlowType &pushingFlow, vector<typename Edge::FlowType> &innerPotencial, vector<typename Edge::FlowType> &outerPotencial, const vector<bool> &isDeleted) {
	if (vertex == layeredNet.source)
		return;

	typename Edge::FlowType lack = pushingFlow;
	
	for (typename Net<Edge>::EdgeIterator &iter = layeredNet.getInnerEdgeIterator(vertex); !iter.isEnd(); iter.move()) {
		Edge *edge = iter.get();

		if (edge->capacity == 0 || isDeleted[edge->from])
			continue;

		typename Edge::FlowType pushment = min<typename Edge::FlowType>(lack, edge->recidualCapacity());
		lack -= pushment;
		edge->flow += pushment;
		edge->reverseEdge->flow -= pushment;
		outerPotencial[edge->from] -= pushment;
		innerPotencial[edge->to] -= pushment;

		pushFlowFromSource(layeredNet, edge->from, pushment, innerPotencial, outerPotencial, isDeleted);

		if (lack == 0)
			break;
	}
}

template <class Edge>
typename Edge::FlowType findBlockingFlowMKM (Net<Edge> &layeredNet) {
	// Initialize potencials:
	vector<typename Edge::FlowType> innerPotencial(layeredNet.getVerticesCount());
	vector<typename Edge::FlowType> outerPotencial(layeredNet.getVerticesCount());

	for (typename Edge::IndexType vertex = 0; vertex < layeredNet.getVerticesCount(); vertex ++) {
		innerPotencial[vertex] = countPotencial(layeredNet, layeredNet.getConstInnerEdgeIterator(vertex));
		outerPotencial[vertex] = countPotencial(layeredNet, layeredNet.getConstOuterEdgeIterator(vertex));
	}


	typename Edge::FlowType blockingFlow = 0;
	vector<bool> isDeleted(layeredNet.getVerticesCount(), false);

	unsigned i = 0;

	while (true) {
		if (isDeleted[layeredNet.source] || isDeleted[layeredNet.sink])
			break;

		for (typename Edge::IndexType vertex = 0; vertex < layeredNet.getVerticesCount(); vertex ++)
			if (!isDeleted[vertex] && getPotencial(layeredNet, vertex, innerPotencial, outerPotencial) == 0)
				deleteVertex(layeredNet, vertex, innerPotencial, outerPotencial, isDeleted);

		typename Edge::IndexType root = layeredNet.source;

		for (typename Edge::IndexType vertex = 0; vertex < layeredNet.getVerticesCount(); vertex ++)
			if (!isDeleted[vertex] && getPotencial(layeredNet, vertex, innerPotencial, outerPotencial) <= getPotencial(layeredNet, root, innerPotencial, outerPotencial))
				root = vertex;

		/*cout << endl;
		cout << "iteration " << (i ++) << ":" << endl;
		printNet(layeredNet, cout << endl << endl);
		cout << "deleted: ";
		for (typename Edge::IndexType vertex = 0; vertex < layeredNet.getVerticesCount(); vertex ++)
			cout << (isDeleted[vertex] ? 1 : 0) << " ";
		cout << "potencials: ";
		for (typename Edge::IndexType vertex = 0; vertex < layeredNet.getVerticesCount(); vertex ++)
			cout << getPotencial(layeredNet, vertex, innerPotencial, outerPotencial) << " ";
		cout << "; root: " << root << endl;
		cout << endl << endl << endl;*/
		
		typename Edge::FlowType rootPotencial = getPotencial(layeredNet, root, innerPotencial, outerPotencial);

		pushFlowToSink(layeredNet, root, rootPotencial, innerPotencial, outerPotencial, isDeleted);
		pushFlowFromSource(layeredNet, root, rootPotencial, innerPotencial, outerPotencial, isDeleted);


		blockingFlow += rootPotencial;
	}

	return blockingFlow;
}


// Global blockingFlow -> maxFlow algorithm:

template <class Edge>
Net<Edge> buildLayeredNetwork (const Net<Edge> &net) {
	// BFS init:
	queue<typename Edge::IndexType> verticesQueue;
	vector<bool> used(net.getVerticesCount(), false);
	verticesQueue.push(net.source);

	// Layered Net init:
	Net<Edge> layeredNet(net.getVerticesCount());
	layeredNet.source = net.source;
	layeredNet.sink = net.sink;
	vector<typename Edge::IndexType> layers(net.getVerticesCount(), numeric_limits<typename Edge::IndexType>::max());
	layers[net.source] = 0;

	// BFS:
	while (!verticesQueue.empty()) {
		typename Edge::IndexType vertex = verticesQueue.front();
		verticesQueue.pop();
	
		if (used[vertex])
			continue;

		used[vertex] = true;
		
		typename Net<Edge>::EdgeIterator iter = net.getConstOuterEdgeIterator(vertex);

		for (iter.setBegin(); !iter.isEnd(); iter.move()) {
			Edge *edge = iter.get();

			if (edge->recidualCapacity() > 0 && layers[edge->from] + 1 <= layers[edge->to]) {
				verticesQueue.push(edge->to);
				
				Edge recidualEdge = *edge;
				recidualEdge.capacity = edge->recidualCapacity();
				recidualEdge.flow = 0;
				layeredNet.addEdge(recidualEdge);
				layers[edge->to] = layers[edge->from] + 1;
			}
		}
	}

	return layeredNet;
}

template <class Edge>
void transwerFlowFromLayeredNetworkToNetwork (Net<Edge> &layeredNet, Net<Edge> &net) {
	// BFS init:
	queue<typename Edge::IndexType> verticesQueue;
	vector<bool> used(net.getVerticesCount(), false);
	verticesQueue.push(net.source);

	// Layered Net init:
	vector<typename Edge::IndexType> layers(net.getVerticesCount(), numeric_limits<typename Edge::IndexType>::max());
	layers[net.source] = 0;

	// BFS:
	while (!verticesQueue.empty()) {
		typename Edge::IndexType vertex = verticesQueue.front();
		verticesQueue.pop();

		if (used[vertex])
			continue;

		used[vertex] = true;
		
		typename Net<Edge>::EdgeIterator iter = net.getConstOuterEdgeIterator(vertex);
		typename Net<Edge>::EdgeIterator &layeredNetIter = layeredNet.getOuterEdgeIterator(vertex);
		layeredNetIter.setBegin();

		for (iter.setBegin(); !iter.isEnd() && !layeredNetIter.isEnd(); iter.move()) {
			Edge *edge = iter.get();

			if (edge->recidualCapacity() > 0 && layers[edge->from] + 1 <= layers[edge->to]) {
				verticesQueue.push(edge->to);

				layers[edge->to] = layers[edge->from] + 1;

				while (layeredNetIter.get()->capacity == 0)
					layeredNetIter.move();
				
				iter.get()->flow += layeredNetIter.get()->flow;
				iter.get()->reverseEdge->flow -= layeredNetIter.get()->flow;
				layeredNetIter.move();	
			}
		}
	}
}

template <class Edge>
typename Edge::FlowType findMaxFlowWithAugmentionPaths (Net<Edge> &net) {
	typename Edge::FlowType maxFlow = 0;

	while (true) {
		Net<Edge> layeredNet = buildLayeredNetwork(net);
		typename Edge::FlowType blockingFlow = findBlockingFlowMKM(layeredNet);

		if (blockingFlow == 0)
			break;

		else {
			transwerFlowFromLayeredNetworkToNetwork(layeredNet, net);
			maxFlow += blockingFlow;
		}
	}

	return maxFlow;
}


// My custom Edge:

template <typename FirstType = unsigned, typename SecondType = long long>
struct Edge {
	typedef FirstType IndexType;
	typedef SecondType FlowType;
	IndexType from;
	IndexType to;
	FlowType flow;
	FlowType capacity;
	Edge *reverseEdge;

	Edge (const IndexType &from = -1, const IndexType &to = -1, const FlowType &capacity = -1) {
		this->from = from;
		this->to = to;
		this->flow = 0;
		this->capacity = capacity;
	}

	FlowType recidualCapacity () const {
		return capacity - flow;
	}

	void increaseFlow (const FlowType &delta) {
		this->flow += delta;
		reverseEdge->flow -= delta;
	}

	Edge getReverse () const {
		return Edge(to, from, 0);
	}

	void print (ostream &os = cout) const {
		os << from << " -> " << to << " (" << flow << "/" << capacity << ")";
	}
};


// Main:

int main () {
	unsigned verticesCount, edgesCount;
	cin >> verticesCount >> edgesCount;

	Net<Edge<unsigned, long long> > net(verticesCount);
	net.source = 0;
	net.sink = verticesCount - 1;

	for (unsigned i = 0; i < edgesCount; i ++) {
		unsigned from, to;
		long long capacity;
		cin >> from >> to >> capacity;
		net.addEdge(Edge<unsigned, long long>(from, to, capacity));
	}

	cout << findMaxFlowWithAugmentionPaths(net) << endl;

	return 0;
}



Measured memory_bytes: 3484