#include<fstream>
#define NMAX 5000
#define inf 25000
using namespace std;
int d[inf];       //ut hossza                    d
int s[inf];       //elozo szomszedja             pre
//int t[inf];       //megneztem-e vagy sem?        M
int a[NMAX][NMAX],n;
int Bellman_Ford();
int Belmann_Ford()
 {
  int i,j,k,ok=0;
  for (i=1;i<=n;i++)
    {
     ok=0;
     for (j=1;j<=n;j++)
	for (k=1;k<=n;k++)
	   if (a[j][k]!=inf && d[k]>d[j]+a[j][k])
	     {
	      d[k]=d[j]+a[j][k];
	      s[k]=j;
	      ok=1;
	     }
     if (!ok)
       break;
    }
  for (j=1;j<=n;j++)
     for (k=1;k<=n;k++)
	if (a[j][k]!=inf && d[k]>d[j]+a[j][k])
	  return 0;
  return 1;
 }

int main()
 {
  int i,j,x,k,l,o,min,hely,m;

//inicializalas

  ifstream be ("dijkstra.in");
  be>>n>>m;
  x=1;
  for (i=1;i<=n;i++)
     for (j=i+1;j<=n;j++)    //mindent vegtelenre allitunk
	a[i][j]=a[j][i]=inf;
  for (i=1;i<=m;i++)
     {
      be>>k>>l>>o;
      a[k][l]=o;             //az elek sulyat betesszuk
     }
  for (i=1;i<=n;i++)
     {
      d[i]=a[x][i];          //az elso el szomszedait beallitjuk
      s[i]=x;
     }
  be.close();
  d[x]=0;s[x]=0;//t[x]=1;
//vege inicializalas
  min=Bellman_Ford();
  ofstream ki ("dijkstra.out");
  for (i=2;i<=n;i++)
     ki<<d[i]<<" ";
  ki<<'\n';
//vege kereses
  ki.close();
  return 0;
  
 }