#include<stdio.h>
#define input "dijkstra.in"
#define output "dijkstra.out"
#define NMAX 10001
int n,m;
int g[NMAX][NMAX]={{0}};

void open()
{
	freopen(input,"r",stdin);
	freopen(output,"w",stdout);
}
void read()
{
	int x,y,z;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		g[x][y]=z;
	}
}

void royfloyd()
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(g[i][k]&&g[k][j]&&(g[i][k]+g[k][j]<g[i][j]||!g[i][j])&&i!=j)
					g[i][j]=g[i][k]+g[k][j];
}

void a_fish()
{
	for(int i=2;i<=n;i++)
		printf("%d ",g[1][i]);
}

int main()
{
	open();
	read();
	royfloyd();
	a_fish();
	return 0;
}