#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

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

int n,m,i,j,nr,ok,np,vmx=1000000,nv,rez;
int d[1024],t[1024],c[1024][1024],v[1024];
vector<int> ad[1024];
deque<int> q;

void make_bf()
{
	q.push_back(1);
	d[1]=1;	t[1]=0;
	while(!q.empty())
	{
		nr=q.front();
		q.pop_front();
		for(int j:ad[nr])
			if(c[nr][j] && d[j]==0)
			{
				d[j]=d[nr]+1;	t[j]=nr;
				q.push_back(j);
			}
	}
}
int update()
{
	int st=0,x,mn=vmx;
	for(auto j:ad[n])
		if(d[j]<mn && c[j][n]>0)
			mn=d[j], st=j;
	
	if(st==0)	return 0;
	int take=vmx;
	x=n;
	t[n]=st;
	nv=0;
	while(x>1)
	{
		mn=t[x];
		take=min(take, c[mn][x]);
		x=mn;
	}
	x=n;
	while(x>1)
	{
		mn=t[x];
		c[mn][x]-=take;
		c[x][mn]+=take;
		if(c[mn][x]==0)	v[++nv]=x;
		x=mn;
	}
	for(int i=1;i<=nv;i++)
	{
		mn=vmx;
		st=v[i];
		for(int j:ad[st])
			if(d[j] && d[j]<mn && c[j][st])
				mn=d[j], t[st]=j;
		
		d[st]=mn+1;
		if(st==t[t[st]])
			rez+=take, take=0;
	}
	return take;
}

int main() {
	
	fin>>n>>m;
	while(m--)
	{
		fin>>i>>j>>nr;
		c[i][j]+=nr;
		ad[i].push_back(j);
		ad[j].push_back(i);
	}
	make_bf();
	
	ok=1;
	while(ok)
	{
		ok=update();
		rez+=ok;
	}
	fout<<rez<<"\n";
}