#include<bits/stdc++.h>
using namespace std;
typedef long long int Long;
typedef long long int ll;
//typedef int ll;
typedef ll ft;
typedef set<int> si;
typedef long long Long;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<Long>vl;
typedef pair<int,int>pii;
typedef pair<Long,Long>pll;
typedef pair<string,int>psi;
typedef pair<double,double>pdd;
#define get getchar_unlocked
#define put putchar_unlocked
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz size()
#define ln length()
#define repstl(i, s) for (__typeof((s).end())i=(s).begin();i!=(s).end();++i)
#define debug1(s,a) cout << s << " " << a << " " << endl;
#define debug2(s,a,b) cout << s << " " << a << " " << b << " " << endl
#define debug3(s,a,b,c) cout << s << " " << a << " " << b << " " << c << " " << endl;
#define debug4(s,a,b,c,d) cout << s << " " << a << " " << b << " " << c << " " << d << " " << endl;
#define debug5(s,a,b,c,d,e) cout << s << " " << a << " " << b << " " << c << " " << d << " " << e << " " << endl;
#define PI 3.1415926535897932384626433832795
#define FO freopen ("out.txt", "w", stdout)
#define FI freopen ("in.txt", "r", stdin)
#define ref(i,a,n) for(int i=a;i<=n;i++)
#define reb(i,n,a) for(int i=n;i>=a;i--)
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
#define gi(n) scanf("%d",&n)
#define gii(n) scanf("%lld",&n)
#define gc(c) scanf(" %c",&c)
#define gs(s) scanf(" %s",s);
#define pi(n) printf("%d",n)
#define pii(n) printf("%lld",n)
#define pc(c) printf("%c",c)
#define ps printf(" ")
#define pn printf("\n")
#define pl(a) printf("%s",a)
#define l(a) 2*a+1
#define r(a) 2*a+2
#define left(a,b) a,(a+b)/2
#define right(a,b) (a+b)/2+1,b
#define mid(a,b) (a+b)/2
void gl(char *str){register char c=0;register int i=0;while(c<33)c=get();while(c!='\n'){str[i]=c;c=get();i=i+1;}str[i]='\0';}
void gfi(ft &x) {register ft c = get(); x = 0; ft sn=1;for(;(c<48 || c>57);c = get()) if(c=='-') sn=-1;for(;c>47 && c<58;c = get()) {x = (x<<1) + (x<<3) + c - 48;}x*=sn;}
//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction

#define N 5010

vi adj[N],cost[N];
ll residual[N][N],duplicate[N][N],MAX=numeric_limits<ll>::max(),flow,maxFlow,n,m;

struct node {
	ll pre,cur,Flow;
	bool visit;
}V[N];

typedef struct node nod;

struct cmp {
	bool operator() (nod x,nod y) {
		return x.Flow<y.Flow;
	}
};

void findPath() {
	ref(i,1,n) {
		V[i].cur=i;
		V[i].pre=-1;
		V[i].visit=false;	
	}
	priority_queue<nod,vector<nod>,cmp> q;
	V[1].Flow=MAX;
	q.push(V[1]);
	while(!q.empty()) {
		ll pre,cur,Flow,curFlow;
		pre=q.top().cur;
		Flow=q.top().Flow;
		V[pre].visit=true;
		q.pop();
		if(pre==n) {
			flow=Flow;
			break;
		}
		rep(i,adj[pre].sz) {
			cur=adj[pre][i];	
			if(!V[cur].visit && residual[pre][cur]>0) {
				curFlow=min(Flow,residual[pre][cur]);
				V[cur].Flow=curFlow;
				V[cur].pre=pre;
				q.push(V[cur]);
			}
		}
	}
	ll cur,pre;
	cur=n;
	while(V[cur].pre!=-1) {
		pre=V[cur].pre;
		residual[pre][cur]-=flow;
		residual[cur][pre]+=flow;
		cur=pre;
	}
}

int main() {
	gfi(n);gfi(m);
	rep(i,m) {
		ll u,v,c;
		gfi(u);gfi(v);gfi(c);
		if(u==v) continue;
		if(duplicate[u][v]) {
			residual[u][v]+=c;cost[u][duplicate[u][v]-1]+=c;
			residual[v][u]+=c;cost[v][duplicate[v][u]-1]+=c;
		} else {
			adj[u].pb(v);cost[u].pb(c);residual[u][v]+=c;duplicate[u][v]=adj[u].sz;
			adj[v].pb(u);cost[v].pb(c);residual[v][u]+=c;duplicate[v][u]=adj[v].sz;
		}	
	}
	maxFlow=0;
	findPath();
	while(flow) {
		maxFlow+=flow;
		flow=0;
		findPath();
	}
	cout << maxFlow << endl;
	return 0;
}