#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 x,y,i,j,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<=n;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]);
	cout<<x<<" ";
	}
}

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