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

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

void build(){ int i,j,x,y,cost;
in>>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(i=1;i<=m;i++){ in>>x>>y>>cost;
									 c[x][y]=cost;
								 }
//in>>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]);
			 out<<x<<" ";
		 }
}

int main(){
int i;
build();
init();
dijkstra();
for(i=1;i<=n;i++)  out<<d[i]<<" ";
out<<endl;
//for(i=1;i<=n;i++)   if(s[i]){ out<<" drumul pana la "<<i<<" este ";
														 //	drum(i);
														 //	out<<endl;
														}
											// else  out<<" Nu exista drum la nodul "<<i<<endl;
return 0;
}