#include <iostream>
#include <fstream>
#include <queue>
#define MAX 1000
#define forever 1
using namespace std;
int parents[MAX];
bool done[MAX];
int capacity_matrix[MAX][MAX];
int flux_matrix[MAX][MAX];
int get_minimum_flux(int drum_ameliorare[], int k){
	int i, min = capacity_matrix[drum_ameliorare[1]][drum_ameliorare[0]] - 
	flux_matrix[drum_ameliorare[1]][drum_ameliorare[0]];
	
	for (i = 1; i < k; i++){
		if (capacity_matrix[drum_ameliorare[i+1]][drum_ameliorare[i]] - 
		flux_matrix[drum_ameliorare[i+1]][drum_ameliorare[i]] < min){
			min = capacity_matrix[drum_ameliorare[i+1]][drum_ameliorare[i]] - 
			flux_matrix[drum_ameliorare[i+1]][drum_ameliorare[i]];
		}
	}
	return min;
}
void adjuste_capacity_matrix(int drum_ameliorare[],int k, int flux_min){
	int i;
	for(i = 0; i < k; i++){
		flux_matrix[drum_ameliorare[i+1]][drum_ameliorare[i]] += flux_min;
		flux_matrix[drum_ameliorare[i]][drum_ameliorare[i+1]] -= flux_min;
	}
}
bool breadth_first_search(int source, int dest){
	// source == primul nod
	// dest == ultimul nod
	queue<int> queue;
	queue.push(source);
	int i;
	bool ok = false;
	while(!queue.empty()){
		int node = queue.front();
		queue.pop();
		if (node != dest){
			for (i = 0; i < MAX; i++){
				if (capacity_matrix[node][i] - flux_matrix[node][i] > 0 && done[i] == false){
					queue.push(i);
					parents[i] = node;
					done[i] = true;
					ok = true;
				}
			}
		}
	}
	return ok;
}
void init_capacity_matrix(int capacity_matrix[MAX][MAX]){

	int i, j;
	for (i = 0; i < MAX; i++){
		done[i] = false;
		parents[i] = -2;
		for( j = 0; j < MAX; j++){	
			capacity_matrix[i][j] = 0;
			flux_matrix[i][j] = 0;
		}
	}
}
int main(){

	ifstream fin("maxflow.in");
	ofstream fout("maxflow.out");
	int number_of_nodes, number_of_edges, i, k;
	int node1, node2, capacity, father;
	int drum_ameliorare[MAX], flux_min, flux = 0;
	bool ok;
	init_capacity_matrix(capacity_matrix);
	fin>>number_of_nodes>>number_of_edges;
	for(i = 0; i < number_of_edges; i++){
		fin>>node1>>node2>>capacity;
		capacity_matrix[node1-1][node2-1] = capacity;
	}
	parents[0] = -1;
	while (forever){
		//cout<<"ruleaza"<<"\n";
		ok = breadth_first_search(0,number_of_nodes-1);
		// pot avea mai multe drumuri de ameliorare
		// ASTA-I CU BONUS!
		// parcurg vectorul de noduri si ma intreb daca nodul i nu il are fiu pe dest
		// daca il are fiu pe dest construiesc drumul si ajustez fluxul + flux_matrix
		// cand termin de parcurs vectorul abia atunci mai fac un bfs :D
		
		if(ok == false){
			// nu mai exista drum de ameliorare :D
			cout<<flux<<"\n";
			fout<<flux<<"\n";
			break;
		}else{
			// s-a mai gasit un drum de ameliorare
			
			for (i = 1; i < number_of_nodes; i++){
				if (capacity_matrix[i][number_of_nodes-1] - flux_matrix[i][number_of_nodes-1] > 0){
					
					father = i;
					drum_ameliorare[0] = number_of_nodes - 1;
					k = 1;
					while(father != 0){
						drum_ameliorare[k++] = father;
						father = parents[father];
					}
					drum_ameliorare[k] = 0;
					flux_min = get_minimum_flux(drum_ameliorare,k);
					flux += flux_min;
					// reduc capacitatile
					adjuste_capacity_matrix(drum_ameliorare,k, flux_min);
				}
			}
			// refac vectorii de parinti si de noduri marcate pt un alt bfs
			for(i = 0; i < MAX; i++){
				done[i] = false;
				parents[i] = -2;
			}
			parents[0] = -1;
		}
		
	}
	return  0;	
}