#include <fstream.h>
#define INFINIT 3500

int a[178][178];
unsigned int n;
long m;
int t[20],viz[20],d[20];

void citire(){
	int x,y,z;
	ifstream f("dijkstra.in");
	f>>n>>m;
	for(int i=1;i<=m;i++){
		f>>x>>y>>z;
		a[x][y]=z;
	}
	f.close();
}

void afisare(){
	ofstream g("dijkstra.out");
	for(int i=2;i<=n;i++) g<<d[i]<<" ";
	g.close();
}

int getmin(){
	int min=INFINIT;
	int nd=0,i;
	for(i=1;i<=n;i++)
		if(!viz[i] && d[i]<min){
			min=d[i];
			nd=i;
		}
	return nd;
}

void dijkstra(int start){
	int i;
	viz[start]=1;
	for(i=1;i<=n;i++){
		if(a[start][i]!=0) d[i]=a[start][i];
		else d[i]=INFINIT;
	}
        d[start]=0;

	int nodmin;
	nodmin=getmin();
	while(nodmin){
		viz[nodmin]=1;
		for(i=1;i<=n;i++)
			if(d[i]>d[nodmin]+a[nodmin][i] && a[nodmin][i]){
				d[i]=d[nodmin]+a[nodmin][i];
				t[i]=nodmin;
			}
		nodmin=getmin();
	}
}

int main(){
	citire();
	dijkstra(1);
	afisare();
	return 0;
}