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


int a[1000][1000],viz[1000],val[1000],n,m;


void dijkstra(int x)
{
	int i,min,k,ok=0;
	for(i=1;i<=n;i++)
	val[i]=a[x][i];
	viz[1]=1;
	while(ok==0)
	{
	min=INT_MAX;
	for(i=2;i<=n;i++)
	if(val[i]<min&&viz[i]==0)
	{
	min=val[i];
	k=i;
	}
	viz[k]=1;
	if(min==INT_MAX)
	ok=1;
	for(i=2;i<=n;i++)
	{
		if(a[k][i]!=INT_MAX)
		{
			if(a[k][i]+min<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]=INT_MAX;
	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]==INT_MAX)
	g<<" 1";
	else
	g<<" "<<val[i];
	g<<'\n';
}

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