#include <stdio.h>

int q[5000],qnre=0,qp=0,qc[5000]={0};
inline void add(int x)
{
	q[(qp+qnre)%5000]=x;
	++qnre;
	qc[x]=1;
}
inline int get()
{
	int e=q[qp];
	qc[e]=0;
	qnre--;
	qp++;
	if(qp==100) qp=0;
	return e;
}
inline int qempty()
{
	if(qnre) return 0;
	return 1;
}
int a[5000][5000];
int n,m;
void read_data()
{
	freopen("dijkstra.in","r",stdin);
	scanf("%d%d",&n,&m);
	int i,x,y,c;
	for(i=0;i<m;++i)
	{
		scanf("%d%d%d",&x,&y,&c);
		a[x][y]=a[y][x]=c;
	}
	fclose(stdin);
}
inline int qin(int x)
{
	return qc[x];
}
#define infinity 100000
int d[5000];
inline void init_d()
{
	for(int i=0;i<5000;++i) d[i]=infinity;
}
void bf(int x)
{
	add(x);
	d[x]=0;
	int e,i;
	while(!qempty())
	{
		e=get();
		for(i=1;i<=n;++i) //toate nodurile
		{
			if(a[e][i]) //am drum pana la acest nod? (vecin?)
			{
				if(d[i]>d[e]+a[e][i])
				{
					if(!qin(i)) add(i);
					d[i]=d[e]+a[e][i];
				}
			}
		}
	}
}
inline void write_answer()
{
	freopen("dijkstra.out","w",stdout);
	for(int i=2;i<=n;++i) printf("%d ",d[i]);
	fclose(stdout);
}
int main()
{
	read_data();
	init_d();
	bf(1);
	write_answer();
	return 0;
}