#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int n,m;
int v[5005],t[5005],mn[5005],nrmc[1002],viz[1005];
vector<int> mc[1002];
int cmc[1002][1002],bob;
long long s;
void parc()
{
	int k=1,l=1;
	v[k]=1;
	int i,j;
	mn[k]=200000000;
	viz[1]=1;
	while(k<=l)
	{
		if(v[k]==n)
		{
			bob=0;
			j=k;
			while(j>1)
			{
				cmc[v[j]][v[t[j]]]+=mn[k];
				cmc[v[t[j]]][v[j]]-=mn[k];
				j=t[j];
			}
		}
		else
			for(i=0;i<nrmc[v[k]];i++)
				if(cmc[v[k]][mc[v[k]][i]]&&(viz[mc[v[k]][i]]==0||mc[v[k]][i]==n))
				{
					viz[mc[v[k]][i]]=1;
					v[++l]=mc[v[k]][i];
					t[l]=k;
					if(mn[k]>cmc[v[k]][mc[v[k]][i]]) mn[l]=cmc[v[k]][mc[v[k]][i]];
					else mn[l]=mn[k];
				}
		k++;
	}
}
int main()
{
	freopen("maxflow.in","r",stdin);
	freopen("maxflow.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i,a,b,c;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		mc[a].push_back(b);
		mc[b].push_back(a);
		nrmc[a]++,nrmc[b]++;
		cmc[a][b]=c;
	}
	bob=0;
	while(bob==0)
	{
		bob=1;
		for(i=1;i<=n;i++)
			viz[i]=0;
		parc();
	}
	for(i=1;i<=n;i++)
		s=s+cmc[n][i];
	printf("%lld",s);
	
	
	return 0;
}