#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 Edge;
bool tryToPush(Edge*);
void initialize();

class EdgeComparator {

public:
	bool operator() (Edge*, Edge*);
};

class VertexComparator {

public:
	bool operator() (Vertex*, Vertex*);
};

struct Edge {

	Vertex* tail;
	Vertex* head;
	int currentCapacity;
	Edge* invertedEdge;

	Edge(Vertex* tailToSet, Vertex* headToSet, int capacity) {

		tail = tailToSet;
		head = headToSet;
		currentCapacity = capacity;
	}
};

class Vertex {

public:
	std::set<Edge*, EdgeComparator, std::allocator<Edge*> > neighbours;
	std::vector<Edge*> incidentFromEdges;
	int currentEdge;
	int index;
	int excess;
	int label;

	Vertex(int indexToSet) {

		index = indexToSet;
		currentEdge = 0;
		excess = 0;
		label = 0;
		incidentFromEdges = std::vector<Edge*>();
	}

	void addIncidentFromEdge(Edge* incidentEdge) {

		incidentFromEdges.push_back(incidentEdge);
		neighbours.insert(incidentEdge);
	}

	void changeExcess(int delta) {

		excess += delta;
	}

	int getIndex() {
		return index;
	}
 
	Edge* getEdgeIfAlreadyExists(Edge* edge) {

		std::set<Edge*, EdgeComparator, std::allocator<Edge*> >::iterator result = neighbours.find(edge);

		if(result != neighbours.end()) {
			return *result;
		} else {
			return NULL;
		}
	}

	Edge* getNextEdge() {

		if(currentEdge == incidentFromEdges.size()) {
			return NULL;
		}

		return incidentFromEdges[currentEdge];
	}

	void moveToNextEdge() {

		if(currentEdge == incidentFromEdges.size()) {
			currentEdge = 0;
			return;
		}

		++currentEdge;
	}

	bool hasExcess() {

		return excess > 0;
	}

	int getExcess() {
		return excess;
	}

	int getLabel() {

		return label;
	}
};

bool EdgeComparator::operator() (Edge* first, Edge* 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;

int N, M;

int main() {

	freopen("maxflow.in","r",stdin);
	freopen("maxflow.out","w",stdout);

	scanf("%d %d",&N,&M);

	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];
		Edge* edge = new Edge(tail, head, capacity);

		Edge* edgeFromVertex = tail->getEdgeIfAlreadyExists(edge);
		if(edgeFromVertex == NULL) {
			Edge* invertedEdge = new Edge(head, tail, 0);

			edge->invertedEdge = invertedEdge;
			invertedEdge->invertedEdge = edge;

			tail->addIncidentFromEdge(edge);
			head->addIncidentFromEdge(invertedEdge);
		} else {
			edgeFromVertex->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()) {
		Edge* edge = vertex->getNextEdge();
		if(edge == NULL) {
			vertex->label++;
			vertex->moveToNextEdge();
		} else {
			bool headBecameWithExcess = tryToPush(edge);
			
			if(headBecameWithExcess && (edge->head->index != N) && (edge->head->index != 1)) {
				newVerticesWithExcess.push_back(edge->head);
			}
		}
	}

	return newVerticesWithExcess;
}

bool tryToPush(Edge* edge) {

//printf("1) (%d, %d) (%d, %d) %d\n", edge->tail->index, edge->tail->label, edge->head->index, edge->head->label, edge->currentCapacity);
//usleep(100000);

	if(!edge->tail->hasExcess() 
		|| (edge->currentCapacity == 0)
		|| (edge->tail->getLabel() - 1 != edge->head->getLabel())) {

//printf("LOL %d\n", edge->tail->currentEdge);
		edge->tail->moveToNextEdge();
		return false;
	}

	bool result = !edge->head->hasExcess();

	int epsilon = std::min(edge->currentCapacity, edge->tail->getExcess());

	edge->currentCapacity -= epsilon;
	edge->invertedEdge->currentCapacity += epsilon;
	edge->tail->changeExcess(-epsilon);
	edge->head->changeExcess(epsilon);

//printf("2) (%d, %d) (%d, %d) %d\n", edge->tail->index, edge->tail->label, edge->head->index, edge->head->label, epsilon);

	if(edge->currentCapacity == 0) {
		edge->tail->moveToNextEdge();
	}

	return result && (edge->head->label<N);
}

void initialize() {

	Vertex* source = vertexByIndex[0];
	source->label = 1;

	Edge* edge = source->getNextEdge();
	while(edge != NULL) {
		source->excess = INF;
		bool headBecameWithExcess = tryToPush(edge);

		if(headBecameWithExcess) {
			verticesWithExcess.push(edge->head);
		}

		edge = source->getNextEdge();
	}

	source->label = N;
	source->excess = 0;
}