#include <algorithm>
#include <stdio.h>
#include <queue>
#include <vector>
#include <set>
#include <memory>
#include <unistd.h>
int INF = 1000000000;
class Vertex;
std::vector<Vertex*> dischargeVertex(Vertex*);
class Arc;
bool tryToPush(Arc*);
void initialize();
class ArcComparator {
public:
	bool operator() (Arc*, Arc*);
};
class VertexComparator {
public:
	bool operator() (Vertex*, Vertex*);
};
struct Arc {
	Vertex* tail;
	Vertex* head;
	int currentCapacity;
	Arc* invertedArc;
	Arc(Vertex* tailToSet, Vertex* headToSet, int capacity) {
		tail = tailToSet;
		head = headToSet;
		currentCapacity = capacity;
	}
};
class Vertex {
public:
	std::set<Arc*, ArcComparator, std::allocator<Arc*> > neighbours;
	std::vector<Arc*> incidentFromArcs;
	int currentArc;
	int index;
	int excess;
	int label;
	Vertex(int indexToSet) {
		index = indexToSet;
		currentArc = 0;
		excess = 0;
		label = 0;
		incidentFromArcs = std::vector<Arc*>();
	}
	void addIncidentFromArc(Arc* incidentArc) {
		incidentFromArcs.push_back(incidentArc);
		neighbours.insert(incidentArc);
	}
	void changeExcess(int delta) {
		excess += delta;
	}
	int getIndex() {
		return index;
	}
	Arc* getArcIfAlreadyExists(Arc* arc) {
		std::set<Arc*, ArcComparator, std::allocator<Arc*> >::iterator result = neighbours.find(arc);
		if(result != neighbours.end()) {
			return *result;
		} else {
			return NULL;
		}
	}
	Arc* getNextArc() {
		if(currentArc == incidentFromArcs.size()) {
			return NULL;
		}
		return incidentFromArcs[currentArc];
	}
	void moveToNextArc() {
		if(currentArc == incidentFromArcs.size()) {
			currentArc = 0;
			return;
		}
		++currentArc;
	}
	bool hasExcess() {
		return excess > 0;
	}
	int getExcess() {
		return excess;
	}
	int getLabel() {
		return label;
	}
};
bool ArcComparator::operator() (Arc* first, Arc* second) {
	return first->head->getIndex() < second->head->getIndex();
}
bool VertexComparator::operator() (Vertex* first, Vertex* second) {
	return first->getLabel() < second->getLabel();
}
std::priority_queue<Vertex*, std::vector<Vertex*>, VertexComparator> verticesWithExcess;
std::vector<Vertex*> vertexByIndex;
std::vector<int> nrOfVerticesPerLayer;
int N, M;
int main() {
	freopen("maxflow.in","r",stdin);
	freopen("maxflow.out","w",stdout);
	scanf("%d %d",&N,&M);
	nrOfVerticesPerLayer = std::vector<int>(N + 1, 0);
	nrOfVerticesPerLayer[0] = N - 1;
	nrOfVerticesPerLayer[N] = 1;
	for(int i=1; i<=N; ++i) {
		Vertex* vertex = new Vertex(i);
		vertexByIndex.push_back(vertex);
	}
	for(int i=1; i<=M; ++i) {
		int x,y,capacity;
		scanf("%d %d %d",&x,&y,&capacity);
		Vertex* tail = vertexByIndex[x-1];
		Vertex* head = vertexByIndex[y-1];
		Arc* arc = new Arc(tail, head, capacity);
		Arc* arcFromVertex = tail->getArcIfAlreadyExists(arc);
		if(arcFromVertex == NULL) {
			Arc* invertedArc = new Arc(head, tail, 0);
			arc->invertedArc = invertedArc;
			invertedArc->invertedArc = arc;
			tail->addIncidentFromArc(arc);
			head->addIncidentFromArc(invertedArc);
		} else {
			arcFromVertex->currentCapacity = capacity;
		}
	}
	initialize();
	while(!verticesWithExcess.empty()) {
		Vertex* vertexToDischarge = verticesWithExcess.top();
		verticesWithExcess.pop();
		std::vector<Vertex*> newVerticesWithExcess = dischargeVertex(vertexToDischarge);
		for(std::vector<Vertex*>::iterator it = newVerticesWithExcess.begin(); it != newVerticesWithExcess.end(); it++) {
			verticesWithExcess.push(*it);
		}
	}
	printf("%d", vertexByIndex[N-1]->getExcess());
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}
std::vector<Vertex*> dischargeVertex(Vertex* vertex) {
	std::vector<Vertex*> newVerticesWithExcess;
	while(vertex->label < N && vertex->hasExcess()) {
		Arc* arc = vertex->getNextArc();
		if(arc == NULL) {
			int minLabel = N;
			for(std::vector<Arc*>::iterator it = vertex->incidentFromArcs.begin(); it != vertex->incidentFromArcs.end(); it++) {
				Arc* arc = *it;
				if(arc->currentCapacity > 0 && (arc->head->label + 1) < minLabel) {
					minLabel = arc->head->label + 1;
				}
			}
			nrOfVerticesPerLayer[vertex->label]--;
			if(nrOfVerticesPerLayer[vertex->label] == 0){
				while(!verticesWithExcess.empty() && verticesWithExcess.top()->label > vertex->label){
					nrOfVerticesPerLayer[verticesWithExcess.top()->label]--;
					nrOfVerticesPerLayer[N]++;
					verticesWithExcess.top()->label = N;
					verticesWithExcess.pop();
				}
				vertex->label = N;
				nrOfVerticesPerLayer[N]++;
				break;
			}
			vertex->label = minLabel;
			nrOfVerticesPerLayer[minLabel]++;
			vertex->moveToNextArc();
		} else {
			bool headBecameWithExcess = tryToPush(arc);
			if(headBecameWithExcess && (arc->head->index != N) && (arc->head->index != 1)) {
				newVerticesWithExcess.push_back(arc->head);
			}
		}
	}
	return newVerticesWithExcess;
}
bool tryToPush(Arc* arc) {
//printf("1) (%d, %d) (%d, %d) %d\n", arc->tail->index, arc->tail->label, arc->head->index, arc->head->label, arc->currentCapacity);
//usleep(100000);
	if(!arc->tail->hasExcess()
		|| (arc->currentCapacity == 0)
		|| (arc->tail->getLabel() - 1 != arc->head->getLabel())) {
//printf("LOL %d\n", arc->tail->currentArc);
		arc->tail->moveToNextArc();
		return false;
	}
	bool result = !arc->head->hasExcess();
	int epsilon = std::min(arc->currentCapacity, arc->tail->getExcess());
	arc->currentCapacity -= epsilon;
	arc->invertedArc->currentCapacity += epsilon;
	arc->tail->changeExcess(-epsilon);
	arc->head->changeExcess(epsilon);
//printf("2) (%d, %d) (%d, %d) %d\n", arc->tail->index, arc->tail->label, arc->head->index, arc->head->label, epsilon);
	if(arc->currentCapacity == 0) {
		arc->tail->moveToNextArc();
	}
	return result && (arc->head->label<N);
}
void initialize() {
	Vertex* source = vertexByIndex[0];
	source->label = 1;
	Arc* arc = source->getNextArc();
	while(arc != NULL) {
		source->excess = INF;
		bool headBecameWithExcess = tryToPush(arc);
		if(headBecameWithExcess) {
			verticesWithExcess.push(arc->head);
		}
		arc = source->getNextArc();
	}
	source->label = N;
	source->excess = 0;
}