#include<stdio.h>
const int inf=1e9;
int main()
{
   
	int m,n,i,j;
	int book[10];	int t1,t2,t3;
	int min;
	int a[10][10];
	int dis[10];
	scanf("%d%d",&m,&n);//输入有m个点，n条边
	for(i=1;i<=m;i++)//形成一个方阵，不能走的路变成inf 到自身的距离改为1
		for(j=1;j<=m;j++)
			if(i==j)	a[i][j]=0;
			else a[i][j]=inf;
	for(i=1;i<=n;i++){
   scanf("%d%d%d",&t1,&t2,&t3);//输入边
	a[t1][t2]=t3;
	}
	
	for(j=1;j<=m;j++)
	dis[j]=a[1][j];	//把1到别的点的距离交给一个一维数组dis
	for(i=1;i<=m;i++)//把用过的点变成1
	book[i]=0;
	book[1]=0;
	for(i=1;i<=n-1;i++)
	{
   
		min=inf;	int u;
		for(j=1;j<=n;j++)
		{
   
			if(min>dis[j]&&book[j]==0)//找出距离最近的点并且要是没有用过的
				{
   
					min=dis[j];
					u=j;
				}
		}
			book[u]=1;	
		for(j=1;j<=n;j++)
		{
   
			if(a[u][j]!=inf)
			{
   
				if(dis[j]>dis[u]+a[u][j])
				dis[j]=dis[u]+a[u][j];	//啊哈算法里说这个叫做松弛
			}
		}
	}
	for(i=1;i<=m;i++)//把最小的距离输出出来
	printf("%10d",dis[i]);
 }