#include<iostream>
#include<fstream>
using namespace std;
#define F 1000000000
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int a[1401][1401],n,r,d[1401],s[1401],m;

void citire(){
	int x,y,c;
	in>>n>>m;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(i!=j)
				a[i][j]=F;
	for(int i=1; i<=m; i++){
		in>>x>>y>>c;
		a[x][y]=c;
	}
}

void dijkstra(int r){
	s[r]=1;
	for(int i=1; i<=n; i++)
		d[i]=a[r][i];
	for(int j=1; j<n; j++){
		int min=F;
		int poz;
		for(int i=1; i<=n; i++)
			if(d[i]<min && !s[i]){
				min=d[i];
				poz=i;
			}
		s[poz]=1;
		for(int i=1; i<=n; i++)
			if(d[i]>d[poz]+a[poz][i] && !s[i]){
				d[i]=d[poz]+a[poz][i];
				
			}
	}
}

int main(){
	int r=1;
	citire();
	dijkstra(r);
	for(int i=2; i<=n; i++)
		out<<d[i]<<" ";
	return 0;
}