#include<cstdio>
#include<vector>
using namespace std;
int n,m,d[50001],h[50001],poz[50001],x,y,c,i,vf;
const int lim=500000000;
struct mystruct{int first;int second;};
mystruct aux;
vector<mystruct> a[50001];
char chr[30];

inline void change(int x,int y)
{
	int a;
	a=h[x];h[x]=h[y];h[y]=a;
	poz[h[x]]=x;poz[h[y]]=y;
}

void heapup(int i)
{
	if(i<=1) return;
	int t=(i>>1);
	if(d[h[i]]<d[h[t]]){
		change(i,t);
		heapup(t);}
}
void heapdown(int i)
{
	int st,dr,t=(i<<1);
	if(t<=m){
		st=h[t];
		if(t+1<=m) dr=h[t+1];
		else dr=st;
		if(d[dr]<d[st]) t=t+1;
		if(d[h[i]]>d[h[t]]){
			change(i,t);
			heapdown(t);}
	}
}

inline void build()
{
	for(i=1;i<=n;i++){
		h[i]=i;
		d[i]=lim;
		poz[i]=i;}
	d[1]=0;
}

inline void get()
{
	int i;
	gets(chr);
	i=0;
	while(chr[i]<'0'||chr[i]>'9') i++;
	x=y=c=0;
	while(chr[i]>='0'&&chr[i]<='9') 
		x=x*10+chr[i++]-'0';
	while(chr[i]<'0'||chr[i]>'9') i++;
	while(chr[i]>='0'&&chr[i]<='9') 
		y=y*10+chr[i++]-'0';
	while(chr[i]<'0'||chr[i]>'9') i++;
	while(chr[i]>='0'&&chr[i]<='9') 
		c=c*10+chr[i++]-'0';


}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	for(i=1;i<=m;i++){
		get();
		aux.first=y;
		aux.second=c;
		a[x].push_back(aux);}

	m=n;
	build();
	while(m>0){
		change(1,m);
		m--;
		heapdown(1);
		vf=h[m+1];
		if(d[vf]==lim)break;
		x=a[vf].size();
		for(i=0;i<x;i++){
			y=a[vf][i].first;
			c=a[vf][i].second;
			if(d[y]>d[vf]+c){
				d[y]=d[vf]+c;
				heapup(poz[y]);}
		}
	}

	for(i=2;i<=n;i++)
		if(d[i]<lim)printf("%d ",d[i]);
		else printf("0 ");
	fclose(stdout);
}