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


int c[NM][NM],d[NM],s[NM],prec[NM],n,m,start=1;
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++)
if(d[i]<INF)
	out<<d[i]<<" ";
	else out<<0<<" ";
/*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;
}