#include <stdio.h>
#include <memory.h>

const int maxn = 510;

const int maxint = 1000000000;

int N,M,s,t,ans;
int cap[maxn][maxn],pre[maxn],vis[maxn],map[maxn][maxn];

void dfs1(int v)
{
	vis[v] = 1;
	for (int i=0; i<N; i++)
	{
		if (vis[i]!=1&& cap[v][i]>0)
		{
			dfs1(i);
		}
	}
}

void dfs2(int v)
{
	vis[v] = -1;
	for (int i=0; i<N; i++)
	{
		if (vis[i]==0 && cap[i][v]>0)
		{
			dfs2(i);
		}
	}
}

int ret;
void maxflow()
{
	int u,i,j,height[maxn] = {0},h,ex;
	pre[s] = s;
	u = s;
	while (height[s] < N)
	{
		h = N;
		for (i=0; i<N; i++)
		{
			if (cap[u][i]>0)
			{
				if (height[u] == height[i]+1)
				{
					pre[i] = u;
					u = i;
					if (i==t)
					{
						ex = maxint;
						for (j=t; j!=s; j=pre[j])
							if (ex > cap[pre[j]][j])
								ex = cap[pre[j]][j];
						for (j=t; j!=s; j=pre[j])
							cap[pre[j]][j]-=ex,cap[j][pre[j]]+=ex;
						u = s;
						ret += ex;
					}
					break;
				}
				else if (h>height[i]) h = height[i];
			}
		}
		if (i>=N) height[u] = h+1, u = pre[u];
	}
}


int main()
{
	int i,j,a,b,c;
	scanf("%d%d",&N,&M);
	for (i=0; i<M; i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		map[a][b] = 1;
		cap[a][b] += c;
	}
	s = 0; t = N-1;
	
	maxflow();
	memset(vis,0,sizeof(vis));
	dfs1(s);
	dfs2(t);
	ans = 0;
	for (i=0; i<N; i++)
	{
		if (vis[i]==1)
		{
			for (j=0; j<N; j++)
			{
				if (vis[j]==-1 && map[i][j])
				{
					ans++;
				}
			}
		}
	}
	
	printf("%d\n",ans);
	return 0;
}