import std.stdio, std.conv, std.string, std.bigint;
import std.math, std.random, std.datetime;
import std.array, std.range, std.algorithm, std.container, std.format;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

/*

------------------------------------------------------------

最大流 最大フロー 最小カット Dinic法 ディニック法

------------------------------------------------------------

*/

void main(){
	int n = read.to!int;
	int m = read.to!int;
	
	Node[] nodes;
	foreach(i; 0 .. n) nodes ~= new Node(i);
	debug writeln("nodes:", nodes);
	
	long infty;
	foreach(j; 0 .. m){
		int a = read.to!int - 0;
		int b = read.to!int - 0;
		long c = read.to!int;
		new Edge(nodes[a], nodes[b], c);
		infty += c;
	}
	infty += 100;
	debug writeln("nodes:", nodes);
	debug writeln("infty:", infty);
	
	Node.start = nodes[0];
	Node.terminal = nodes[n - 1];
	
	long ans;
	while(1){
		foreach(nd; nodes) nd.isVisited = 0;
		Node.start.setDepth(0);
		if(! Node.terminal.isVisited) break;
		debug writeln("nodes:", nodes);
		
		while(1){
			long f = Node.start.flow(infty);
			debug writeln("f:", f, " nodes:", nodes);
			if(f > 0) ans += f;
			else break;
		}
		
	}
	
	ans.writeln;
}

class Node{
	static Node[] queue;
	static int iq;
	static Node start, terminal;
	
	long id;
	Edge[] edges;
	bool isVisited;
	int depth;
	bool isStart, isTerminal;
	
	this(long id){
		this.id = id;
	}
	
	void setDepth(int depth){
		if(this.isVisited) return;
		this.isVisited = 1;
		this.depth = depth;
		queue ~= this;
		foreach(ed; edges) if(ed.value > 0) ed.node1.setDepth(depth + 1);
	}
	
	long flow(long value){
		long flow = 0;
		foreach(ed; edges) if(ed.value > 0){
			debug writeln(this.id, "->", ed);
			Node nd = ed.node1;
			long res = min(value, ed.value);
			if(this.depth < nd.depth && nd.depth < terminal.depth){
				res = min(res, nd.flow(res));
			}
			else if(nd.id != terminal.id) continue;
			if(res > 0){
				ed.value -= res;
				ed.inv.value += res;
				flow += res;
				return flow;
			}
			debug writeln(this.id, "->", ed);
		}
		return flow;
	}
	
	override string toString(){
		return id.to!string ~ edges.to!string ~ "(" ~ depth.to!string ~ ")" ~ (isVisited?"v":"") ~ (isStart?"s":"") ~ (isTerminal?"t":"");
	}
}
class Edge{
	Node node0, node1;
	long value;
	Edge inv;
	this(Node node0, Node node1, long value){
		this.node0 = node0, node0.edges ~= this;
		this.node1 = node1;
		this.value = value;
		this.inv = new Edge(this);
		}
	this(Edge inv){
		this.node0 = inv.node1, inv.node1.edges ~= this;
		this.node1 = inv.node0;
		this.value = 0;
		this.inv = inv;
	}
	override string toString(){
		return this.node1.id.to!string ~ "(" ~ value.to!string ~ ")";
	}
}

