#include<fstream>
#include<vector>
#include<queue>
#define mult 1000000
#define dmax 1003
using namespace std;
ifstream in("maxflow.in");
ofstream out("maxflow.out");

int n,m,f[dmax][dmax],t[dmax],mn[dmax],str[dmax],c[dmax][dmax],fm;
bool p[dmax],w[dmax];


vector<int>g[dmax];
vector<int>::iterator it;
vector<int>fr;
vector<int>::iterator ir;

queue<int>q;

void bfs()
{	
	int crt;
	
	q.push(1);
	p[1]=1;
	
	while(!q.empty() )
	{	
		crt=q.front();
		q.pop();
		
		for(it=g[crt].begin();it<g[crt].end();it++)
			if(!p[*it])
				if(f[crt][*it] < c[crt][*it])
				{	q.push(*it);
					p[*it]=1;
					t[*it]=crt;
					mn[*it]=min(mn[crt], c[crt][*it] - f[crt][*it]);
					if(crt==1)
						str[*it]=*it;
					else str[*it]=str[crt];
				}	
		
	}
}


void update(int k)
{	int w;
	
	w=min(mn[k], c[k][n]-f[k][n]);
	f[k][n]+=w;
	
	while(t[k]!=0 )
	{	f[t[k]][k]+=w;
		f[k][t[k]]-=w;
		k=t[k];
	}	
}


int main()
{
	int i,a,b,d;

	in>>n>>m;

	for(i=1;i<=m;i++)	
	{	
		in>>a>>b>>d;
		if(a!=b)
		{	g[a].push_back(b);
			g[b].push_back(a);
			c[a][b]+=d;
		}	
		if(b==n)
			fr.push_back(a);
		
	}
	in.close();
	
	int ok=1,k;
	
	while(ok)
	{	
		for(i=1;i<=n;i++)
		{	t[i]=str[i]=w[i]=p[i]=0;
			mn[i]=mult;
		}
		
		bfs();
		
		k=0;
		for(ir=fr.begin();ir<fr.end();ir++)
		{	
			if(f[*ir][n] < c[*ir][n])
				if(!w[str[*ir]] && mn[*ir]!=mult)
				{	k=1;
					w[str[*ir]]=1;
					update(*ir);
				}
		}	
		if(!k )
			ok=0;
	}	
	
	
	for(ir=fr.begin();ir<fr.end();ir++)
		fm+=f[*ir][n];
		
	out<<fm<<" ";
	
	out.close();
	return 0;
}