#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;
	}
}
void breadth_first_search(int source, int dest){
	// source == primul nod
	// dest == ultimul nod
	queue<int> queue;
	queue.push(source);
	int i;
	while(!queue.empty()){
		int node = queue.front();
		queue.pop();
		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;
			}
		}
	}
}
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;
	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){
		breadth_first_search(0,number_of_nodes-1);
		if(parents[number_of_nodes - 1] == -2){
			// nu mai exista drum de ameliorare :D
			cout<<flux<<"\n";
			fout<<flux<<"\n";
			break;
		}else{
			// s-a mai gasit un drum de ameliorare
			father = parents[number_of_nodes-1];
			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;	
}