#include <stdio.h>
#include <string.h>
#define MAX 50001

typedef long long tipus;
struct adat{
tipus x,c;
adat *next;
adat(){next=0;}
};

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

void sift(tipus x){
tipus fiu,temp;

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

if(fiu>0){
temp=h[x];
h[x]=h[fiu];
h[fiu]=temp;
x=fiu;
}

}while(fiu>0);

}

void perc(tipus x){
tipus key=h[x];

while((x>1)&&(h[x/2]>key)){
h[x]=h[x/2];
x=x/2;
}
h[x]=key;
}

void build(tipus n){
tipus i;
for(i=n/2;i>=1;i--)sift(i);

}

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

}


void dijk(){
adat *p=a[1];
tipus i,mini;
bool lattam[MAX];
memset(lattam,0,sizeof(lattam));
memset(l,-1,sizeof(l));
while(p!=0){l[p->x]=p->c;p=p->next;}
for(i=1;i<n;i++)h[i]=i+1;
nh=n-1;
build(nh);
lattam[1]=1;
for(i=1;i<=n-1;i++){
mini=h[1];
h[1]=h[nh];
nh--;lattam[mini]=1;
p=a[mini];
while(p!=0){
	if((!lattam[p->x])&&(((p->c+l[mini]<l[p->x])&&(l[mini]!=-1))||(l[p->x]==-1))){l[p->x]=p->c+l[mini];}
p=p->next;}

sift(1);
}

}

int main(){
freopen("dijkstra.in","r",stdin);
		freopen("dijkstra.out","w",stdout);
		tipus temp1,temp2,i,temp3;
scanf("%lld %lld",&n,&m);

for(i=1;i<=m;i++){
scanf("%lld %lld %lld",&temp1,&temp2,&temp3);
add(temp1,temp2,temp3);
}

dijk();
for(i=2;i<=n;i++){
	if(l[i]==-1)l[i]=0;
printf("%lld ",l[i]);
}
	return 0;
}