#include<fstream>
#define g 5000
#define G 30000
#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;
  be.close();
  for (i=1;i<=n;i++)
    {
     min=vegtelen;
     for (j=1;j<=n;j++)
	if (d[i]<min && !t[i])
	  {
	   min=d[i]; hely=i;
	  }
     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++)
     ki<<d[i]<<" ";
  ki<<'\n';
  ki.close();
  return 0;
 }