// AOJ GRL_6_A
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#define rep(i,n) for(int i=0; i<(n); i++)

using namespace std;
typedef vector<int> vi;

const int INF = 0x3fffffff;

// template, remove_edge, limit_flow ???????£??????????
// ????????????????°???????????????´???????????´??\C[][]???????????????reset()??????????????????????????????

// ?????§???????±???????(Dinic???)
class Flow{
	public:
		int N;	// ????????°
		vector<vi> F, C, edge;	// F:????????°?????? C:???????????? edge:??£??\????????????

		vi itr, lv;	// itr:??????????????£???????????????  lv:S??????????????¢

		// ????????????????????? n:????????°
		Flow(int n): N(n), F(n,vi(n)), C(n,vi(n)), edge(n) {}

		// f->t????????????c?????????????????????(??????f->t??????????????????????????????????????¨?????????)
		void addEdge(int f, int t, int c){
			addCap(f, t, c);
			edge[f].push_back(t);
			edge[t].push_back(f);
		}

		// f->t??????????????????c?¢???????(c?????????)
		void addCap(int f, int t, int c){
			F[f][t] += c;
			C[f][t] += c;
		}

		// ??????f->t?????¢????????????addEdge()???????????????????????????????????????????????¨??????
		void uniqueEdge(){
			for(auto e: edge){
				sort( e.begin(), e.end() );
				e.erase( unique( e.begin(), e.end() ), e.end() );
			}
		}

		// s????????????????????¢????±?????????????????????????????????¨DFS??§?????????????????????????????¢?´¢??????
		int bfs(int S, int T){
			lv.assign(N, 0);
			queue<int> q;
			q.push(S);
			lv[S] = 1;
			while( !q.empty() ){
				int n = q.front(); q.pop();
				for(auto v: edge[n]) if( !lv[v] && F[n][v] ){
					lv[v] = lv[n] + 1;
					q.push(v);
				}
			}
			return lv[T];
		}

		// ?¢?????????????DFS??§??¢???
		int dfs(int n, int c, int T){
			if( n == T ) return c;
			for(;itr[n] < edge[n].size(); ++itr[n]){
				int v = edge[n][itr[n]];
				if( F[n][v] && lv[v] > lv[n] ){
					int f = dfs(v, min(c, F[n][v]), T);
					F[n][v] -= f;
					F[v][n] += f;
					if(f) return f;
				}
			}
			return 0;
		}

		// ?????§???????±???????(?????¨?????¶??????????????????????????????????????£?????????)
		int maxFlow(int S, int T){
			if( S == T ) return INF;
			int ret = 0;
			while( bfs(S,T) ){
				itr.assign(N,0);
				for(int f; f=dfs(S, INF, T);) ret += f;
			}
			return ret;
		}

		// ??????????????????????????????????????????
		int flow(int f, int t){ return C[f][t] - F[f][t]; }

		// ??£??\?????????????????????????¨???????????????????n=S,T??\????????´?????????????????????1/2????????????????????????????????????
		int flow(int n){
			int ret=0;
			for(int v: edge[n]) ret += abs( flow(n,v) );
			return ret;
		}

		// ??°???????????????????????????
		void reset(){ rep(i,N) rep(j,N) F[i][j] = C[i][j]; }
};

// ????£???????????????????(Ford-Fulkerson???)
class Flow_min{
	public:
		int N;	// ????????°
		vector<vi> F, C, edge;	// F:????????°?????? C:???????????? edge:??£??\????????????

		vi used;	// ??????????????£???????????????

		// ????????????????????? n:????????°
		Flow_min(int n): N(n), F(n,vi(n)), C(n,vi(n)), edge(n) {}

		// f->t????????????c?????????????????????(??????f->t??????????????????????????????????????¨?????????)
		void addEdge(int f, int t, int c){
			F[f][t] = C[f][t] = c;
			edge[f].push_back(t);
			edge[t].push_back(f);
		}

		// f->t??????????????????c?¢???????(???????????§???)
		void addCap(int f, int t, int c){
			F[f][t] += c;
			C[f][t] += c;
		}

		// ?¢?????????????DFS??§??¢???
		int dfs(int n, int c, int T){
			int f = c * (n==T);
			used[n] = 1;
			for(int v: edge[n]) if( !f && F[n][v] && !used[v] ){
				f = dfs(v, min(c, F[n][v]), T);
				F[n][v] -= f;
				F[v][n] += f;
			}
			return f;
		}

		// ???????????????(S,T?????°?????????)
		void maxFlow(int S, int T){
			// if(S==T) return INF;
			while( used.assign(N,0), dfs(S, INF, T) ){}
			// return flow(T);
		}

		// ??????????????????????????????????????????(???????????§???)
		int flow(int f, int t){ return C[f][t] - F[f][t]; }

		// ??£??\?????????????????????????¨???????????????????n=S,T??\????????´?????????????????????1/2????????????????????????????????????
		int flow(int n){
			int ret=0;
			for(int v: edge[n]) ret += abs( C[n][v] - F[n][v] );
			return ret;
		}

		// ??°???????????????????????????(???????????§???)
		void reset(){ rep(i,N) rep(j,N) F[i][j] = C[i][j]; }
};

// ????°??§????

class Flow_min2{
	public:
		int N;	// ????????°
		vector<vi> F, C, e;	// F:????????°?????? C:???????????? e:??£??\????????????
		vi b;	// ??????????????£???????????????
		Flow_min2(int n): N(n), F(n,vi(n)), C(n,vi(n)), e(n) {}
		void addEdge(int f, int t, int c){
			F[f][t] = C[f][t] = c;
			e[f].push_back(t);
			e[t].push_back(f);
		}
		int dfs(int n, int c, int T){
			int f = c * (n==T);
			b[n] = 1;
			for(int v: e[n]) if( !f && F[n][v] && !b[v] ){
				f = dfs(v, min(c, F[n][v]), T);
				F[n][v] -= f;
				F[v][n] += f;
			}
			return f;
		}
		void maxFlow(int S, int T){
			while( b.assign(N,0), dfs(S, INF, T) ){}
		}
		int flow(int n){
			int f=0;
			for(int v: e[n]) f += abs( C[n][v] - F[n][v] );
			return f;
		}
};


int main(){
	int V, E;
	cin >> V >> E;

	Flow fl(V);
	Flow_min2 fm(V);
	rep(i, E){
		int u, v, c;
		cin >> u >> v >> c;
		fl.addEdge( u, v, c );
		fm.addEdge( u, v, c );
	}

//	cout << fl.maxFlow(0, V-1) << endl;
	fm.maxFlow(0, V-1);
	cout << fm.flow(0) << endl;

	return 0;
}

Measured memory_bytes: 3264