//pku1273.cpp
//Drainage Ditches
//ning----flow_bfs
//29/07/06   13:49:05
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#define N 205
#define INF 10000000
int c[N][N];
int f[N][N];
int queue[N*2];
int per[N];
int begin,end;
int visited[N];
int ss,tt;//tt是自己加的汇点,c[m][tt]=INF*N;
int bfs()
{
	int cur,ii,jj,min;
	memset (visited,0,sizeof(visited));
	memset (per,0,sizeof(per));
	begin= end =0;
	per [end]=-1;
	queue[end]=0;
	visited[0]=1;
	end++;
	for(;begin<end;begin++)
	{
		cur=queue[begin];
		for(ii=0;ii<=tt;ii++)
			if(c[cur][ii]>f[cur][ii]&&!visited[ii])
			{
				visited[ii]=1;
				per[ii]=cur;///这里写错了，调了半天。。
				queue[end]=ii;
				end++;
				if(ii==tt)
					goto findWay;
			}
	}
findWay:
	if(!visited[tt])
		return 0;
	min=INF;
	for(ii=end-1;per[ii]!=-1;ii=per[ii])
	{
		if(min>c[per[ii]][ii]-f[per[ii]][ii])
			min=c[per[ii]][ii]-f[per[ii]][ii];
	}	
	for(ii=end-1;per[ii]!=-1;ii=per[ii])
	{
		f[per[ii]] [ii]+=min;
		f[ii] [per[ii]]-=min;
	}
	return 1;
}
int main()	
{
	int m,n;
	int ii,si,ci,ei;
	for(;scanf("%d%d",&n,&m)!=EOF;)
	{
		if(!m)
			break;
		tt=m+1;
		memset(c,0,sizeof(c));
		memset(f,0,sizeof(f));
		for(ii=0;ii<n;ii++)
		{
			scanf("%d%d%d",&si,&ei,&ci);
			c[si][ei]+=ci;
		}
		c[0][1]=INF*N;
		c[m][tt]=INF*N;

		for(;bfs();)
			;
		printf("%d\n",f[0][1]);
	}
	return 0;
}