#include<fstream>
#define inf 10000

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int n, m, st, a[5000][5000], pre[5000], d[5000];
bool M[5000];

void initializare(){
	cin>>n>>m; st= 1;
	for(int i=1; i<=n; ++i)	for(int j=1+i; j<=n; ++j) a[i][j]=a[j][i]=inf;
	while(m--){
		int x, y, z; cin>>x>>y>>z;
		a[x][y]=z;
	}
	
	for(int i=1; i<=n; ++i){ d[i]=a[st][i]; pre[i]=st;}
	pre[st]=0; M[st]=1;
}

int main(){ 
	initializare();
	
	for(int i=1; i<n; ++i){
		int dmax = inf, vfmin;
		for(int j=1; j<=n; ++j){
			if(!M[j] && dmax>d[j]){ 
									dmax=d[j]; vfmin = j;
								}
		}
		M[vfmin]=1;
		for(int j=1; j<=n; ++j){
			if(!M[j] &&  a[vfmin][j] + d[vfmin] < d[j]){
				d[j] = a[vfmin][j] + d[vfmin]; pre[j] = vfmin;
			}
		}
		
	}	
	for(int i=2; i<=n; ++i){
		cout<<d[i]<<"  ";
	}

	return 0;
}