#include <cstdio>
#define N 1001
int a[N][N],n,sol,min,v[5*N],x[5*N],y[5*N],h[N];

void up(int p)
{
	++h[0];
	int q=h[0],w=h[0]/2;
	while ((w!=0)&& (y[p]<y[h[w]]))
	{
		h[q]=h[w];v[h[w]]=q;
		q=w,w/=2;
	}
	h[q]=p;
	v[p]=q;
}

void del(int p)
{
	/*
	h[p]=h[h[0]];
	v[h[p]]=p;*/
	int nou,q=p,w=p/2,j;
	
	if (p==h[0]) 
		{--h[0];return ;}
		j=h[h[0]],nou=y[h[h[0]]];
	--h[0];
	
	while ((w!=0) && (nou<y[h[w]]))
	{
		h[q]=h[w];v[h[q]]=q;
		q=w;w/=2;
	}
	while (q*2<=h[0])
	{
		int ok1=(nou>y[h[q*2]]),ok2=((q*2<h[0]) && (nou>y[h[q*2+1]]));
		if (ok1&&ok2)
		{
			if (y[h[q*2]]<y[h[q*2+1]])
				h[q]=h[q*2],v[h[q]]=q,q=q*2; else
				h[q]=h[q*2+1],v[h[q]]=q,q=q*2+1;
		} else
			if (ok1)
				h[q]=h[q*2],v[h[q]]=q,q=q*2; else
					if (ok2)
						h[q]=h[q*2+1],v[h[q]]=q,q=q*2+1; else
							break;
	}
	
	h[q]=j;v[j]=q;
}


void flow(int p)
{
	if (p==n) {sol+=y[h[1]]-min;min=y[h[1]];return ;}
	int i=1,nod,c;
	
	while ((i<=a[p][0]) && (y[h[1]]>min))
		if (a[p][i])
		{
		y[a[p][i]]+=min; //normalizez costul muchiei a[p][i];
		c=y[a[p][i]];nod=x[a[p][i]]; //c=cost
		up(a[p][i]);  //v[a[p][i]]=pozitia in heap a muchiei a[p][i]
		flow(nod);  
		y[a[p][i]]-=min;
		del(v[a[p][i]]);
		if (!y[a[p][i]]) a[p][i]=0;
		}  else ++i;
		
}
			
		
		
		
		

int main()
{
	int i,j,m,k;
	
	freopen("maxflow.in","r",stdin);
	freopen("maxflow.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d %d",&j,&x[i],&y[i]);
		a[j][++a[j][0]]=i;
	}
	for (i=1;i<=a[1][0];++i)
	{
		min=0;
		//c=y[a[p][i]];nod=x[a[p][i]];
		h[0]=0;
		up(a[1][i]);
		flow(x[a[1][i]]);
	}
	printf("%d",sol);
	
return 0;
}