#include<stdio.h>
#include<vector>
#define kkt 1000000000
using namespace std;
int n,m,num;
unsigned short int heap[50005];
unsigned short int x1[50005];
int rez[50005];
vector<unsigned short int> v[50005];
vector<unsigned short int> a[50005];
void urca(unsigned short int i)
{
	unsigned short int j,aux;
	j=i>>1;
	while(j&&rez[heap[i]]<rez[heap[j]])
	{
	aux=heap[i];
	heap[i]=heap[j];
	heap[j]=aux;
	x1[heap[j]]=j;
	x1[heap[i]]=i;
	i=j;
	j=j>>1;
	}
}
void coboara(unsigned short int i)
{
	unsigned short int j,k,aux;
	while(i<num)
	{
		j=i<<1;
		k=i;
		if(j<=num && rez[heap[j]]<rez[heap[k]])
			k=j;
		j=(i<<1)+1;
		if(j<=num && rez[heap[j]]<rez[heap[k]])
			k=j;
		if(rez[heap[k]]<rez[heap[i]])
		{
		aux=heap[k];
		heap[k]=heap[i];
		heap[i]=aux;
		x1[heap[k]]=k;
		x1[heap[i]]=i;
		i=k;
		}
		else
		return;
	}
}
void dijkstra(unsigned short int val)
{
	unsigned short int i,j,k,c=v[val].size();
	rez[val]=0;
	for(i=0;i<c;i++)
	{
	heap[++num]=v[val][i];
	rez[heap[num]]=a[val][i];
	x1[v[val][i]]=num;
	urca(num);
	}
	while(num)
	{
	c=v[heap[1]].size();
	j=heap[1];
	for(i=0;i<c;i++)
		if(rez[j]+a[j][i]<rez[v[j][i]])
		{
		k=v[j][i];
		if(rez[k]==kkt)
			{
			rez[k]=rez[j]+a[j][i];
			heap[++num]=k;
			x1[k]=num;
			urca(num);
			}
			else
			{
			rez[k]=rez[j]+a[j][i];
			urca(x1[k]);
			}
			}
		x1[heap[num]]=1;
		heap[1]=heap[num];
		num--;
		coboara(1);
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int i;
	unsigned short int j,x,y,z;
	char s[20];
	scanf("%d%d\n",&n,&m);
	for(i=1;i<=m;i++)
	{
		x=y=z=0;
		gets(s);
		for(j=0;s[j]!=' ';j++)
			x=x*10+s[j]-'0';
		for(j++;s[j]!=' ';j++)
			y=y*10+s[j]-'0';
		for(j++;s[j];j++)
			z=z*10+s[j]-'0';
		v[x].push_back(y);
		a[x].push_back(z);
	}
	for(i=1;i<=n;i++)
		rez[i]=kkt;
	dijkstra(1);
	for(i=2;i<=n;i++)
		if(rez[i]!=kkt)
			printf("%d ",rez[i]);
		else
			printf("0");
	return 0;
}