#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 + 10, 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->hasExcess()) {
		Arc* arc = vertex->getNextArc();
		if(arc == NULL) {
			int minLabel = 2*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;
}