// 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 pair<int,int> pii;
typedef vector<int> vc;

const int INF = 0x3fffffff;

// ?????§???????±???????(Dinic??????bfs()??????????????¨Ford-Fulkerson???)
class Flow{
	public:
		int N;	// ????????°
		vector<vc> F, C, edge;	// F:????????°?????? C:???????????? edge:??£??\????????????
		vector<bool> bf;	// ??????????????£???????????????
		vector<int> lv;	// S??????????????¢

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

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

		// ??????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> que;
			que.push(S);
			lv[S] = 1;
			while( !que.empty() ){
				int n = que.front(); que.pop();
				for(auto v: edge[n]) if( !lv[v] && F[n][v] ){
					lv[v] = lv[n] + 1;
					que.push(v);
				}
			}
			return lv[T];
		}

		// ?¢?????????????DFS??§??¢???
		int dfs(int n, int c, int T){
			if( n == T ) return c;
			bf[n] = true;
			for(int v: edge[n]) if( F[n][v] && !bf[v] && lv[v] > lv[n] ){	// ??????????????¶??????????????¨bfs()?????????????????????
				int f = dfs(v, min(c, F[n][v]), T);
				F[n][v] -= f;
				F[v][n] += f;
				if( f > 0 ) return f;
			}
			return 0;
		}

		// ?????§???????±???????
		int maxFlow(int S, int T){
			if( S == T ) return INF;
			int ret = 0;
			while( bfs(S,T) )	// bfs()???????????´?????????????????????????????????
				for(int add; bf.assign(N,0), add = dfs(S, INF, T);) ret += add;
			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<vc> F, C, edge;	// F:????????°?????? C:???????????? edge:??£??\????????????
		vector<bool> bf;	// ??????????????£???????????????

		// ????????????????????? n:????????°
		Flow_min(int n): F(n,vc(n)), C(n,vc(n)), N(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);
		}

		// ?¢?????????????DFS??§??¢???
		int dfs(int n, int c, int T){
			int f = c * (n==T);
			bf[n] = true;
			for(int v: edge[n]) if( !f && F[n][v] && !bf[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){
			while( bf.assign(N,0), dfs(S, INF, 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]; }
};

int main(){
	int V, E;
	cin >> V >> E;
	Flow fl(V);
	Flow_min fm(V);
	rep(i, E){
		int u, v, c;
		cin >> u >> v >> c;
		fl.addEdge( u, v, c );
		fm.addEdge( u, v, c );
		fl.uniqueEdge();
		fl.maxFlow(0, V-1);
		//cout << u << ":" << v << " " << fl.flow(u,v) << endl;
	}

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

	return 0;
}

Measured memory_bytes: 3272