#include<fstream.h>
#include<limits.h>
#define NM 100001
#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,x,y,cost,j;
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++)
		 if(d[i]<INF) out<<d[i]<<" ";
		 else out<<0<<" ";

	  return 0;
	  }