#include<stdio.h>
#include<vector>
#define inf 1000000000
using namespace std;
int n,m,nr;
unsigned short int h[50005],p[50005];
int d[50005];
vector<unsigned short int> v[50005];
vector<int> c[50005];

void up(unsigned short int i)
{
	unsigned short int j=i>>1,aux;
	while(j && d[h[i]]<d[h[j]])
	{
		aux=h[i];
		h[i]=h[j];
		h[j]=aux;
		p[h[j]]=j;
		p[h[i]]=i;
		i=j;
		j=j>>1;
	}
}

void down(unsigned short int i)
{
	unsigned short int j,k,aux;
	while(i<nr)
	{
		j=i<<1;
		k=i;
		if(j<=nr && d[h[j]]<d[h[k]])
			k=j;
		j=(i<<1)+1;
		if(j<=nr && d[h[j]]<d[h[k]])
			k=j;
		if(d[h[k]]<d[h[i]])
		{
			aux=h[k];
			h[k]=h[i];
			h[i]=aux;
			p[h[k]]=k;
			p[h[i]]=i;
			i=k;
		}
		else
			return;
	}
}

void dijkstra(int s)
{
	unsigned short int i,j,k,lim=v[s].size();
	d[s]=0;
	for(i=0;i<lim;i++)
	{
		h[++nr]=v[s][i];
		d[h[nr]]=c[s][i];
		p[v[s][i]]=nr;
		up(nr);
	}
	while(nr)
	{
		lim=v[h[1]].size();
		j=h[1];
		for(i=0;i<lim;i++)
			if(d[j]+c[j][i]<d[v[j][i]])
			{
				k=v[j][i];
				if(d[k]==inf)
				{
					d[k]=d[j]+c[j][i];
					h[++nr]=k;
					p[k]=nr;
					up(nr);
				}
				else
				{
					d[k]=d[j]+c[j][i];
					up(p[k]);
				}
			}
		p[h[nr]]=1;
		h[1]=h[nr];
		nr--;
		down(1);
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int i,x,y,z;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		v[x].push_back(y);
		c[x].push_back(z);
	}
	for(i=1;i<=n;i++)
		d[i]=inf;
	dijkstra(1);
	for(i=2;i<=n;i++)
		if(d[i]!=inf)
			printf("%d ",d[i]);
		else
			printf("0 ");
	return 0;
}