#include<fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define infinit 1000000000
int d[1400],a[1400][1400],s[1400],n,m,r=1;
void citire() {
  int x,y,c;
  fin>>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++) {
	  fin>>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-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&&d[i]>d[poz]+a[poz][i]) 
			  d[i]=d[poz]+a[poz][i];
		}
	}
}
int main() {
	citire();
	dijkstra(r);
	for(int i=2;i<=n;i++)
		if(d[i]==infinit) 
			fout<<"0 ";
		else fout<<d[i]<<" ";
return 0;
}