#include<fstream.h>
#include<limits.h>
#define INF (INT_MAX-10)/2
#define NM 1001
#define end "\n"

int c[NM][NM],d[NM],s[NM],prec[NM],n,start=1,m;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void build(){
int i,j,x,y,cost;
fin>>n>>m;
for(i=1;i<=n;i++)
		for(j=1;j<=n;j++) c[i][j]=INF;
for(i=1;i<=n;i++) c[i][i]=0;
for(j=1;j<=m;j++){fin>>x>>y>>cost;
c[x][y]=cost;
}
//fin>>start;
}


void init(){
int i;
s[start]=1;
for(i=1;i<=n;i++) {d[i]=c[start][i];
									 if(d[i]<INF&&i!=start) prec[i]=start;}
}

int minim(){
int m=INF*2,i,k;
for(i=1;i<=n;i++)
	 if(!s[i]&&d[i]<m){m=d[i];
										 k=i;
										 }
return k;
}

void dijkstra(){
int k,i,dc,nrs=1,gata=0;
do{k=minim();
	 if(d[k]==INF||nrs==n) gata=1;
	 else{ s[k]=1;
				nrs++;
				for(i=1;i<=n;i++)
					 if(!s[i]){dc=d[k]+c[k][i];
										if(dc<d[i]){d[i]=dc;
										prec[i]=k;
										}
										}
}
}while(!gata);
}


void drum(int x){
if(x){drum(prec[x]);
fout<<x<<" ";
}
}


int main(){
int i;
build();
init();
dijkstra();
for(i=2;i<=n;i++)
	if(d[i]<INF)  fout<<d[i]<<" ";
	else fout<<0<<" ";

fout<<endl;
//for(i=1;i<=n;i++)
	//if(s[i]) {fout<<"drumul pana la "<<i<<" este ";
	//drum(i);
	//fout<<endl;
	//}
	//else fout<<" nu exista drum la nodul "<<i<<endl;
return 0;
}