#include<stdio.h>
#define M 250010
#define N 50010
#define INF 100000000
struct muchie{
	int x,y,c;
};
int n,d[N],*a[N],*b[N],poz[N],h[N];
muchie v[M];
void citire(){
	int m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
		++d[v[i].x];
	}
	for(int i=1;i<=n;++i){
		a[i]=new int[d[i]+1];
		a[i][0]=0;
		b[i]=new int[d[i]+1];
		b[i][0]=0;
		d[i]=INF;
		poz[i]=i;
		h[i]=i;
	}
	for(int i=0;i<m;++i){
		a[v[i].x][++a[v[i].x][0]]=v[i].y;
		b[v[i].x][++b[v[i].x][0]]=v[i].c;
	}
	/*
	for(int i=1;i<=a[1][0];++i)
		d[a[1][i]]=b[1][i];
	*/
	d[1]=0;
}
inline void schimb(int x,int y){
	int aux=h[x];
	h[x]=h[y];
	h[y]=aux;
	poz[h[x]]=x;
	poz[h[y]]=y;
}
void reconstituie(int i,int k){
	int min=i,st=i<<1,dr=st+1;
	if(st<=k && d[h[st]]<d[h[min]])
		min=st;
	if(dr<=k && d[h[dr]]<d[h[min]])
		min=dr;
	if(min!=i){
		/*
		int aux=d[i];
		d[i]=d[min];
		d[min]=aux;
		poz[i]=min;
		poz[min]=i;
		*/
		schimb(i,min);
		reconstituie(min,k);
	}
}
void urca(int i){
	if(i!=1 && d[h[i]]<d[h[i>>1]]){
		schimb(i,i>>1);
		urca(i>>1);
	}
}
void construieste(){
	//int min=(a[1][0] < (n>>1) ? a[1][0] : (n>>1));
	for(int i=(n>>1);i>=1;--i)
		reconstituie(i,n);
}
void dijkstra(){
	//s[1]=true;
	int x,nh=n,i;
	while(nh && d[h[1]]!=INF){
		x=h[1];
		schimb(1,nh);
		--nh;
		reconstituie(1,nh);
		for(i=1;i<=a[x][0];++i)
			if(d[a[x][i]]>d[x]+b[x][i]){
				d[a[x][i]]=d[x]+b[x][i];
				urca(poz[a[x][i]]);
			}
	}
}
void scrie(){
	for(int i=2;i<n;++i)
		printf("%d ",d[i]==INF ? 0 : d[i]);
	printf("%d\n",d[n]==INF ? 0 : d[n]);
}
int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	construieste();
	dijkstra();
	scrie();
	return 0;
}