#include<fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int a[22000][22000],viz[50000],val[50000],n,m;

void dijkstra(int x)
{
	int i,min,k,ok=0;
	for(i=1;i<=n;i++)
	val[i]=a[x][i];
	viz[x]=1;
	while(ok==0)
	{
		min=1002;
		for(i=1;i<=n;i++)
		if(viz[i]==0&&val[i]<min)
		{
			min=val[i];
			k=i;
		}
		if(min==1002)
		ok=1;
		viz[k]=1;
		for(i=1;i<=n;i++)
		{
			if(a[k][i]!=1002&&min+a[k][i]<val[i])
			val[i]=a[k][i]+min;
		}
	}
}

void citire()
{
	int i,j,x,y,z;
	f>>n>>m;
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	a[i][j]=1002;
	for(i=1;i<=m;i++)
	{
	f>>x>>y>>z;
	a[x][y]=z;
	}
}

void afisare()
{
	int i;
	for(i=2;i<=n;i++)
	if(val[i]==1002)
	g<<"0 ";
	else
	g<<val[i]<<" ";
}

int main()
{
	citire();
	dijkstra(1);
	afisare();
}