#include <bits/stdc++.h>
using namespace std;

#define cin fin
#define cout fout

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

struct FlowNetwork{

	int n;
	
	struct edge{
		int from, to;
		int cap, flow;
		int cost;
		
	};
	vector<edge> edges;

	vector<vector<int>> out;
	vector<int> ledge;
	vector<int> flow;

	FlowNetwork(int n, int s, int t): n(n), s(s), t(t){
		out.resize(n+1);
		ledge.resize(n+1);
		flow.resize(n+1);
	}

	void addEdge(int from, int to, int cap, int cost){
		edges.push_back({from, to, cap, 0, cost});
		out[from].push_back(edges.size()-1);
		edges.push_back({to, from, 0, 0, -cost});
		out[to].push_back(edges.size()-1);
	}

	int s, t;

	int pushFlow(){
		queue<int> q;
		fill(ledge.begin(), ledge.end(), -1);
		fill(flow.begin(), flow.end(), 0);
		flow[s]=1e9;	
		ledge[s]=-2;
		q.push(s);
		while(!q.empty()){
			int x=q.front();
			q.pop();
			for(auto it:out[x]){
				auto e=edges[it];
				if(ledge[e.to]!=-1||e.cap==e.flow) continue;
				ledge[e.to]=it;
				flow[e.to]=min(flow[x], e.cap-e.flow);
				if(e.to==t) return flow[e.to];
				q.push(e.to);
			}
		}
		return 0;
	}

	int getflow(){
		int flow=0;
		while(int newFlow=pushFlow()){
			flow+=newFlow;
			int cr=t;
			while(cr!=s){
				edges[ledge[cr]].flow+=newFlow;
				edges[ledge[cr]^1].flow-=newFlow;
				cr=edges[ledge[cr]].from;
			}
		}
		return flow;
	}

};

int main(){
	int n, m;
	cin>>n>>m;
	FlowNetwork idk(n, 1, n);
	for(int i=1;i<=m;++i){
		int a, b, c; 
		cin>>a>>b>>c; 
		idk.addEdge(a, b, c, 0);
	}
	cout<<idk.getflow()<<"\n";
}