#include <stdio.h>
#define MAX 50001
const int legn=1 << 30;

struct adat{
int x,c;
adat *next;
adat(){next=0;}
};

int n,nh,m,l[MAX],h[MAX],poz[MAX];
adat *a[MAX];

void add(int x,int y,int c){
adat *p=new adat;
p->x=y;
p->c=c;
p->next=a[x];
a[x]=p;
}

void swap(int x,int y){
int temp;
temp=h[x];
h[x]=h[y];
h[y]=temp;
}

void sift(int x){
int fiu;

do{
	fiu=0;
if(2*x<=nh){
fiu=2*x;
if((2*x+1<=nh)&&(l[h[2*x+1]]<l[h[fiu]]))fiu=2*x+1;
if(l[h[x]]<l[h[fiu]])fiu=0;
}

if(fiu>0){
swap(x,fiu);
poz[h[fiu]]=fiu;
poz[h[x]]=x;
x=fiu;
}

}while(fiu>0);

}

void perc(int x){
int key=l[h[x]],temp=h[x];
while((x>1)&&(l[h[x/2]]>key)){
h[x]=h[x/2];
poz[h[x]]=x;
x=x/2;
}
h[x]=temp;
poz[h[x]]=x;
}


void dijk(){
int i,min;
adat *p;

for(i=2;i<=n;i++){
poz[i]=-1;
l[i]=legn;
}

poz[1]=1;
nh++;h[nh]=1;

while(nh>0){
min=h[1];
swap(1,nh);
poz[h[1]]=1;
nh--;sift(1);

for(p=a[min];p!=0;p=p->next){
	if(l[min]+p->c<l[p->x]){
	l[p->x]=l[min]+p->c;

	if(poz[p->x]!=-1){
	perc(poz[p->x]);
	}else{
	nh++;
	h[nh]=p->x;
	poz[h[nh]]=nh;	
	perc(nh);
	}

}}

}

}

int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	int i,temp1,temp2,temp3;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++){
	scanf("%d %d %d",&temp1,&temp2,&temp3);
	add(temp1,temp2,temp3);
	}

	dijk();

	for(i=2;i<=n;i++){
	if(l[i]==legn)l[i]=0;
	printf("%d ",l[i]);

	}

return 0;
}