#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:
		vector<list<Edge> > outerEdges;
		vector<list<Edge> > 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();
				}

				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]);
			}
		}

		void addEdge (const Edge &edge) {
			Edge reverseEdge = edge.getReverse();
			outerEdges[edge.from].push_back(edge);
			outerEdges[reverseEdge.from].push_back(reverseEdge);
			innerEdges[edge.to].push_back(edge);
			innerEdges[reverseEdge.to].push_back(reverseEdge);
			Edge *edgePointer = &(*prev(outerEdges[edge.from].end()));
			Edge *reverseEdgePointer = &(*prev(outerEdges[reverseEdge.from].end()));
			edgePointer->reverseEdge = reverseEdgePointer;
			reverseEdgePointer->reverseEdge = edgePointer;
		}

		list<Edge>& getOuterEdges (const IndexType &vertex) {
			return outerEdges[vertex];
		}

		list<Edge>& getInnerEdges (const IndexType &vertex) {
			return innerEdges[vertex];
		}

		list<Edge> const & getConstOuterEdges (const IndexType &vertex) const {
			return outerEdges[vertex];
		}

		list<Edge> const & getConstInnerEdges (const IndexType &vertex) const {
			return innerEdges[vertex];
		}

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

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

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

		void print (ostream &os = cout) {
			/*for (IndexType vertex = 0; vertex < getVerticesCount(); vertex ++) {
				if (outerEdges[vertex].size() == 0)
					continue;

				for (const Edge &edge: outerEdges[vertex]) {
					edge.print(cout);
					cout << "; ";
				}

				cout << endl;
			}*/

			for (IndexType vertex = 0; vertex < getVerticesCount(); vertex ++) {
				while (!outerEdgeIterator[vertex].isEnd()) {
					outerEdgeIterator[vertex].get().print();
					cout << " ";
					outerEdgeIterator[vertex].move();
				}

				cout << endl;
				outerEdgeIterator[vertex].setBegin();
			}
		}
};



// Push-relabel algorithm:


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

	for (const Edge& edge: net.getConstOuterEdges(vertex))
		if (edge.recidualCapacity() > 0)
			minHeight = min<typename Edge::IndexType>(minHeight, height[edge.to]);
	
	height[vertex] = minHeight + 1;
}

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

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

		if (iter.isEnd()) {
			lift(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::CapacityType dischargeHighest (Net<Edge> &net) {
	vector<typename Edge::CapacityType> excess(net.getVerticesCount(), 0);
	vector<typename Edge::IndexType> height(net.getVerticesCount(), 0);
	height[net.source] = net.getVerticesCount();

	for (Edge &edge: net.getOuterEdges(net.source)) {
		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::CapacityType maxFlow = 0;

	for (const Edge &edge: net.getConstOuterEdges(net.source))
		maxFlow += edge.flow;
	
	return maxFlow;
}



// M-K-M algorithm:


template <class Edge>
Net<Edge> buildLayeredNet (const Net<Edge> &net) {
	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;

	
	queue<typename Edge::IndexType> verticesQueue;
	vector<bool> used(net.getVerticesCount(), false);
	verticesQueue.push(net.source);

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

		if (used[vertex])
			continue;

		used[vertex] = true;

		for (const Edge &edge: net.getConstOuterEdges(vertex)) {
			if (edge.recidualCapacity() > 0 && layers[edge.from] < layers[edge.to]) {
				verticesQueue.push(edge.to);
				layers[edge.to] = layers[edge.from] + 1;
				layeredNet.addEdge(edge);
			}
		}
	}


	return layeredNet;
}


template <class Edge>
typename Edge::CapacityType countInnerPotencial (const Net<Edge> &net, const typename Edge::IndexType &vertex) {
	typename Edge::CapacityType innerPotencial = 0;

	for (const Edge &edge: net.getConstInnerEdges(vertex))
		innerPotencial += edge.recidualCapacity();

	return innerPotencial;
}

template <class Edge>
typename Edge::CapacityType countOuterPotencial (const Net<Edge> &net, const typename Edge::IndexType &vertex) {
	typename Edge::CapacityType outerPotencial = 0;

	for (const Edge &edge: net.getConstOuterEdges(vertex))
		outerPotencial += edge.recidualCapacity();

	return outerPotencial;
}

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

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

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

template <class Edge>
void deleteVertex (const Net<Edge> &layeredNet, const typename Edge::IndexType &vertex, vector<typename Edge::CapacityType> &innerPotencial, vector<typename Edge::CapacityType> &outerPotencial, vector<bool> &isDeleted) {
	isDeleted[vertex] = true;
	cout << vertex << endl;

	for (const Edge &edge: layeredNet.getConstInnerEdges(vertex)) {
		if (isDeleted[edge.from] || edge.capacity == 0)
			continue;

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

		if (outerPotencial[edge.from] == 0)
			deleteVertex(layeredNet, edge.from, innerPotencial, outerPotencial, isDeleted);
	}

	for (const Edge &edge: layeredNet.getConstOuterEdges(vertex)) {
		if (isDeleted[edge.to] || edge.capacity == 0)
			continue;

		outerPotencial[edge.to] -= edge.recidualCapacity();

		if (innerPotencial[edge.to] == 0)
			deleteVertex(layeredNet, edge.to, innerPotencial, outerPotencial, isDeleted);
	}
}


template <class Edge>
void pushFlowToSink (Net<Edge> &layeredNet, const typename Edge::IndexType &root, const typename Edge::CapacityType &pushingFlow, vector<typename Edge::CapacityType> &innerPotencial, vector<typename Edge::CapacityType> &outerPotencial, vector<bool> &isDeleted) {
	vector<typename Edge::CapacityType> excess(layeredNet.getVerticesCount(), 0);
	excess[root] = pushingFlow;
	queue<typename Edge::IndexType> verticesQueue;
	vector<bool> used(layeredNet.getVerticesCount(), false);
	verticesQueue.push(root);

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

		if (used[vertex])
			continue;

		used[vertex] = true;

		if (vertex == layeredNet.sink)
			break;

		typename Net<Edge>::EdgeIterator &iter = layeredNet.getOuterEdgeIterator(vertex);

		while (excess[vertex] > 0) {
			Edge &edge = iter.get();

			if (edge.recidualCapacity() > 0 && !isDeleted[edge.to]) {
				typename Edge::CapacityType delta = min<typename Edge::CapacityType>(excess[edge.from], edge.recidualCapacity());
				excess[edge.from] -= delta;
				excess[edge.to] += delta;
				edge.flow += delta;
				edge.reverseEdge->flow -= delta;
				outerPotencial[edge.from] -= delta;
				innerPotencial[edge.to] -= delta;

				if (outerPotencial[edge.from] == 0)
					deleteVertex(layeredNet, edge.from, innerPotencial, outerPotencial, isDeleted);

				verticesQueue.push(edge.to);
			}

			else
				iter.move();
		}
	}
}

// Inner Edges - это другой лист а так не надо делать)

template <class Edge>
void pushFlowFromSource (Net<Edge> &layeredNet, const typename Edge::IndexType &root, const typename Edge::CapacityType &pushingFlow, vector<typename Edge::CapacityType> &innerPotencial, vector<typename Edge::CapacityType> &outerPotencial, vector<bool> &isDeleted) {
	vector<typename Edge::CapacityType> lack(layeredNet.getVerticesCount(), 0);
	lack[root] = pushingFlow;
	queue<typename Edge::IndexType> verticesQueue;
	vector<bool> used(layeredNet.getVerticesCount(), false);
	verticesQueue.push(root);

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

		if (used[vertex])
			continue;

		used[vertex] = true;

		if (vertex == layeredNet.source)
			break;

		typename Net<Edge>::EdgeIterator &iter = layeredNet.getInnerEdgeIterator(vertex);

		while (lack[vertex] > 0) {
			Edge &edge = iter.get();

			if (edge.recidualCapacity() > 0 && !isDeleted[edge.from]) {
				typename Edge::CapacityType delta = min<typename Edge::CapacityType>(lack[edge.to], edge.recidualCapacity());
				lack[edge.from] += delta;
				lack[edge.to] -= delta;
				edge.flow += delta;
				edge.reverseEdge->flow -= delta;
				outerPotencial[edge.from] -= delta;
				innerPotencial[edge.to] -= delta;

				if (innerPotencial[edge.to] == 0)
					deleteVertex(layeredNet, edge.to, innerPotencial, outerPotencial, isDeleted);

				verticesQueue.push(edge.from);
			}
			
			else
				iter.move();
		}
	}
}

template <class Edge>
typename Edge::CapacityType setBlockingFlow (Net<Edge> &layeredNet) {
	vector<typename Edge::CapacityType> innerPotencial(layeredNet.getVerticesCount());
	vector<typename Edge::CapacityType> outerPotencial(layeredNet.getVerticesCount());
	vector<bool> isDeleted(layeredNet.getVerticesCount(), false);

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


	typename Edge::CapacityType blockingFlow = 0;

	unsigned i = 0;

	while (true) {
		if (isDeleted[layeredNet.source])
			break;
		
		typename Edge::IndexType root = layeredNet.source;

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


		cout << endl;
		cout << "iteration " << (i ++) << ":" << endl;
		layeredNet.print(cout << endl);
		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;
		

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

		blockingFlow += rootPotencial;
	}

	return blockingFlow;
}


template <class Edge>
void setBlockingFlowToNet (Net<Edge> &net, const Net<Edge> &layeredNet) {
	for (;;) {

	}
}


template <class Edge>
typename Edge::CapacityType MKM (Net<Edge> &net) {
	typename Edge::CapacityType maxFlow = 0;
	typename Edge::CapacityType blockingFlow;

	do {
		Net<Edge> layeredNet = buildLayeredNet(net);
		blockingFlow = setBlockingFlow(layeredNet);


		break;
		maxFlow += blockingFlow;
		setBlockingFlowToNet(net, layeredNet);
	} while (blockingFlow != 0);

	return maxFlow;
}



// My custom Edge:

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

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

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

	void increaseFlow (const CapacityType &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 << ")";
	}
};


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 << dischargeHighest(net) << endl;

	return 0;
}


Measured memory_bytes: 3352