#include <stdio.h>
#include <queue>
using namespace std;
priority_queue<int> z;
#define N 50000
#define M 250000
int q[N],qnre=0,qp=0,qc[N]={0};
int *a[N], *c[N];
struct triplet
{
	int x,y,c;
};
triplet t[M];
inline void add(int x)
{
	q[(qp+qnre)%N]=x;
	++qnre;
	qc[x]=1;
}
inline int get()
{
	int e=q[qp];
	qc[e]=0;
	qnre--;
	qp++;
	if(qp==N) qp=0;
	return e;
}
inline int qempty()
{
	if(qnre) return 0;
	return 1;
}
int n,m;
void read_data()
{
	freopen("dijkstra.in","r",stdin);
	scanf("%d%d",&n,&m);
	int i;
	int v[N]={0};
	for(i=1;i<=m;++i)
	{
		scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].c);
		v[t[i].x]++;
	}
	for(i=1;i<=n;++i)
	{
		a[i]=new int[v[i]+1];
		c[i]=new int[v[i]+1];
		a[i][0]=c[i][0]=0;
	}
	for(i=1;i<=m;i++)
	{
		a[t[i].x][++a[t[i].x][0]]=t[i].y;
		c[t[i].x][++c[t[i].x][0]]=t[i].c;		
	}
	
	fclose(stdin);
}
inline int qin(int x)
{
	return qc[x];
}
#define infinity 1000000000
int d[N];
inline void init_d()
{
	for(int i=0;i<N;++i) d[i]=infinity;
}
void bf(int x)
{
	z.push(x);
	//add(x);
	d[x]=0;
	int e,i;
	while(!z.empty())
	{
		e=z.front();
		//e=get();
		z.pop();
		for(i=1;i<=a[e][0];++i) //toate nodurile adiacente cu e
		{
			if(d[a[e][i]]>d[e]+c[e][i])
			{
				if(!qin(a[e][i])) z.push(a[e][i]);
				d[a[e][i]]=d[e]+c[e][i];
			}
			
		}
	}
}
inline void write_answer()
{
	freopen("dijkstra.out","w",stdout);
	for(int i=2;i<=n;++i) printf("%d ",(d[i]==infinity)?(0):(d[i]));
	fclose(stdout);
}
int main()
{
	read_data();
	init_d();
	bf(1);
	write_answer();
	return 0;
}