#include<fstream.h>
#define g 1005
#define G 1005
#define vegtelen 10000
//using namespace std;
unsigned int a[g][g],d[G],s[G],t[G];

int main()
 {
  ifstream be ("dijkstra.in");
  ofstream ki ("dijkstra.out");
  int n,m,i,j,min,hely,x,y;
  be>>n>>m;
  for (i=1;i<=n;i++)
     for (j=1;j<=n;j++)
	a[i][j]=vegtelen;
  for (i=0;i<m;i++)
    {
     be>>x>>y;
     be>>a[x][y];
    }
  for (i=1;i<=n;i++)
    { d[i]=a[1][i];
      s[i]=1; }
  t[1]=1;
  s[1]=0;d[1]=0;
  be.close();
  for (i=1;i<=n;i++)
    {
     min=vegtelen;
     for (j=1;j<=n;j++)
	if (d[j]<min && !t[j])
	  {
	   min=d[j]; hely=j;
	  }
     t[hely]=1;
     for (j=1;j<=n;j++)
	if (a[hely][j]+min<d[j] && !t[j])
	  {
	   d[j]=a[hely][j]+min;
	   s[j]=hely;
	  }
    }
  for (i=2;i<=n;i++)
    {
       if (d[i]!=vegtelen)
	 ki<<d[i]<<" ";
       else
	 ki<<0<<" ";
    }
  ki<<'\n';
  ki.close();
  return 0;
 }