#include<iostream>
#include<fstream>

using namespace std;

#define infinit 1000000000

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

int a[1400][1400],s[1400],d[1400],n,m;

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

void dijkstra(int r){
	//initializare
	s[r]=1;
	for(int i=1;i<=n;i++)
		d[i]=a[r][i];
	for(int j=1;j<=n-1;j++){
		int min=infinit,poz;
		for(int i=1;i<=n;i++)
			if(s[i]==0 && d[i]<min){
				min=d[i];
				poz=i;
			}
		s[poz]=1;
		for(int i=1;i<=n;i++)
			if(s[i]==0){
				int dc=d[poz]+a[poz][i];
				if(dc<d[i])
					d[i]=dc;
			}
	}
}

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