#include<bits/stdc++.h>
#define pb push_back
#define ft first
#define maxn 1005
#define sd second
#define inf 0x3f3f3f3f
using namespace std;
vector<int>v[maxn];
queue<int>q;
pair<int,int> c[maxn][maxn];
int f[maxn][maxn],cost[maxn],viz[maxn],tt[maxn],n,m,d,s,flux,Cost;
 
void solve(){
	viz[n]=1;
	while(viz[n]){
		q.push(1);
		memset(cost, inf, sizeof(cost));
		memset(viz, 0, sizeof(viz));
		viz[1]=1;cost[s]=0;
		while(!q.empty()){
			int nod=q.front();
			q.pop();
			if(nod==n)
				continue;
			for(int i=0; i<v[nod].size(); i++){
				int dest=v[nod][i];
				if(viz[dest]||f[nod][dest]==c[nod][dest].ft)
					continue;
	//			if(cost[nod]+c[nod][dest].sd<cost[dest]){
					q.push(dest);
					cost[dest]=cost[nod]+c[nod][dest].sd;
					tt[dest]=nod;
					viz[dest]=1;
	//			}
			}
		}
			flux=inf;
			if(!viz[tt[n]] || c[tt[n]][n].ft==f[tt[n]][n])
				continue;
			for(int wh=n; wh!=1; wh=tt[wh])
				flux=min(flux, c[tt[wh]][wh].ft-f[tt[wh]][wh]);
			for(int wh=n; wh!=1; wh=tt[wh])
				f[tt[wh]][wh]+=flux,
				f[wh][tt[wh]]-=flux;
			Cost+=flux;
		}
	cout<<Cost;
}
 
 
int main(){
	freopen("maxflow.in","r",stdin);
	freopen("maxflow.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;//>>s>>d;
	int x,y,z,w;
	while(m--){
		cin>>x>>y>>w;//>>z;
		v[x].pb(y); v[y].pb(x);
		c[x][y].ft=w; c[x][y].sd=z; c[y][x].sd=-z;
	}
	solve();
	return 0;
}