#include <fstream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

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

const int N=1005;
const int inf=0x3f3f3f3f;

int c[N][N],f[N][N],minim,n,m;
int pred[N];
bool use[N];


vector <int> a[N];

bool bfs(int s)
{
	int x;

	minim=inf;
	
	memset(use,false,sizeof(use));
	memset(pred,0,sizeof(pred));
	queue <int> q;
	
	q.push(s);
	use[s]=true;
	
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(vector<int> :: iterator i=a[x].begin();i!=a[x].end();i++)
		{
			
			if(!use[*i] && (c[x][*i]-f[x][*i]>0))
			{
				use[*i]=true;
				pred[*i]=x;
				q.push(*i);
				if(*i==n)
					return true;
			}
			
		}
	}
	return false;
}
/*
int calcmin(int x)
{
	int min=inf;
	while(pred[x])
	{
		if(c[pred[x]][x]-f[pred[x]][x]<min)
			min=c[pred[x]][x]-f[pred[x]][x];
		x=pred[x];
	}
	return min;
}
*/

int calcmin(int x)
{
	int min=c[x][n] - f[x][n];
	while(pred[x])
	{
		if(c[pred[x]][x]-f[pred[x]][x]<min)
			min=c[pred[x]][x]-f[pred[x]][x];
		x=pred[x];
	}
	return min;
}

int main()
{
	int flux,x,y,cst;
	in>>n>>m;
	
	while(m--)
	{
		in>>x>>y>>cst;
		a[x].push_back(y);
		a[y].push_back(x);
		c[x][y]=cst;
	}
	
	flux=0;
	while(bfs(1))
	{
		for(vector<int> :: iterator i=a[n].begin(); i!=a[n].end();i++)
		{
			if(f[*i][n]==c[*i][n] || !use[*i])
				continue;
			if(c[*i][n]>0)
			{
				minim=calcmin(*i);
				flux+=minim;
				f[*i][n]+=minim;
				f[n][*i]-=minim;
				x=*i;
				while(pred[x])
				{
					f[pred[x]][x]+=minim;
					f[x][pred[x]]-=minim;
					x=pred[x];
				}
			}
		}
	}
	
	out<<flux;
	
	return 0;
}