#include <iostream>
#include <fstream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <limits>

using namespace std;

class Graph {
private:
	int _nodes, _edges;
	vector<unordered_map<int, int>> _residual_graph;
	vector<int> _bfs_tree;
	vector<bool> _visited;
	vector<unordered_map<int, int>> _adj_list;

	bool BFS(const int start, const int dest) {

		queue<int> node_queue;
		_visited = vector<bool>(_nodes + 1);
		_bfs_tree = vector<int>(_nodes + 1);

		_bfs_tree[start] = 0;
		_visited[start] = true;
		node_queue.push(start);

		while (!node_queue.empty()) {
			const int node = node_queue.front();
			node_queue.pop();

			for (auto& edge : _residual_graph[node]) {

				if (!_visited[edge.first] && edge.second > 0) {
					_visited[edge.first] = true;
					_bfs_tree[edge.first] = node;
					node_queue.push(edge.first);
				}
			}
		}
		return _visited[dest];
	}
public:
	Graph(int nodes, int edges, vector<unordered_map<int, int>> adj_list) :
		_nodes(nodes),
		_edges(edges),
		_residual_graph(adj_list),
		_adj_list(std::move(adj_list))
	{
		for (int i = 1; i <= _nodes; ++i) {
			for (const auto& edge : _adj_list[i]) {
				if(_residual_graph[edge.first].find(i) == _residual_graph[edge.first].end())
					_residual_graph[edge.first][i] = 0;
			}
		}
	}

	int maxFlow(const int source,const int dest){
		int max_flux = 0;
		while(BFS(source,dest)){
			for (const auto& edge : _residual_graph[dest]) {

				int node = edge.first;
				if (edge.second == _adj_list[node][dest] || !_visited[node])
					continue;

				int flux = numeric_limits<int>::max();
				flux = min(flux, _residual_graph[node][dest]);

				while (_bfs_tree[node] != 0) {
					const int father = _bfs_tree[node];
					flux = min(flux, _residual_graph[father][node]);
					if (flux == 0)
						break;
					node = father;
				}

				if (flux == 0)
					continue;
				max_flux += flux;

				node = edge.first;
				_residual_graph[node][dest] -= flux;
				_residual_graph[dest][node] += flux;
				while (_bfs_tree[node] != 0) {
					const int father = _bfs_tree[node];
					_residual_graph[father][node] -= flux;
					_residual_graph[node][father] += flux;
					node = father;
				}
			}
		}
		return max_flux;
	}
};

int main()
{
	ifstream in("maxflow.in");

	int nodes, edges;
	in >> nodes >> edges;

	vector<unordered_map<int, int>> adj_list(nodes + 1);
	for(int i=0; i<edges; ++i){
		int node1, node2, capacity;
		in >> node1 >> node2 >> capacity;
		adj_list[node1][node2] = capacity;
	}
	in.close();

	Graph flux_time(nodes, edges, adj_list);

	ofstream out("maxflow.out");
	out << flux_time.maxFlow(1,nodes);
	out.close();
}