#include<stdio.h>
#define inf 1000000000
#define xyz 50050
struct muchie{
	int x,y,c;
}muc[250100];
struct heapu{
	int val,nod;
}h[50100];
int d[50100],n,m,hn,fol[50100],poz[50100];
int *nr[50100],*cost[50100];
void citire(){
	int i,j,aux;
	char s[100];
	scanf("%d%d",&n,&m);
	fgets(s,100,stdin);
	for(i=0;i<m;++i){
		fgets(s,100,stdin);
		j=0;
		aux=0;
		while('0'<=s[j] && s[j]<='9')
			aux=aux*10+s[j++]-'0';
		++j;
		muc[i].x=aux;
		aux=0;
		while('0'<=s[j] && s[j]<='9')
			aux=aux*10+s[j++]-'0';
		++j;
		muc[i].y=aux;
		aux=0;
		while('0'<=s[j] && s[j]<='9')
			aux=aux*10+s[j++]-'0';
		muc[i].c=aux;
		++d[muc[i].x];
	}
	for(i=1;i<=n;++i){
		nr[i]=new int [d[i]+1];
		cost[i]=new int [d[i]+1];
		nr[i][0]=0;
		cost[i][0]=0;
		d[i]=inf;
	}
	for(i=0;i<m;++i){
		nr[muc[i].x][++nr[muc[i].x][0]]=muc[i].y;
		cost[muc[i].x][++cost[muc[i].x][0]]=muc[i].c;
	}
}
void schimb(int i,int max){
	h[xyz]=h[max];
	h[max]=h[i];
	h[i]=h[xyz];
}
void downheap(int i){
	int st=i<<1;
	int max=i;
	if(st<=hn && h[max].val>h[st].val)
		max=st;
	++st;
	if(st<=hn && h[max].val>h[st].val)
		max=st;
	if(max!=i){
		schimb(i,max);
		poz[h[max].nod]=max;
		poz[h[i].nod]=i;
		downheap(max);
	}
}
void upheap(int i){
	int sus=i>>1;
	if(i>0 && h[i].val<h[sus].val){
		schimb(i,sus);
		poz[h[sus].nod]=sus;
		poz[h[i].nod]=i;
		upheap(sus);
	}
}
void solve(){
	int i,ax,p;
	h[1].nod=1;
	hn=1;
	while(hn){
		d[h[1].nod]=h[1].val;
		ax=h[1].nod;
		fol[ax]=1;
		h[1]=h[hn];
		h[hn].val=h[hn].nod=0;
		poz[h[1].nod]=1;
		--hn;
		downheap(1);
		for(i=1;i<=nr[ax][0];++i){
			if(!fol[nr[ax][i]]){
				if(poz[nr[ax][i]]==0){
					++hn;
					h[hn].nod=nr[ax][i];
					h[hn].val=cost[ax][i]+d[ax];
					poz[nr[ax][i]]=hn;
					upheap(hn);
				}
				else{
					p=poz[nr[ax][i]];
					if(d[ax]+cost[ax][i]<h[p].val){
						h[p].val=d[ax]+cost[ax][i];
						upheap(p);
					}
				}
			}
		}
	}
}
void scrie(){
	for(int i=2;i<n;++i)
		printf("%d ",d[i]!=inf?d[i]:0);
	printf("%d\n",d[n]!=inf?d[n]:0);
}	
int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	solve();
	scrie();
	fclose(stdin);
	fclose(stdout);
	return 0;
}