#include <fstream>
#include <cstdio>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int maxN=20005;
int a[maxN][maxN],n,m,k=1;
int viz[maxN], d[maxN], tata[maxN];
const int infinit = 16000;

void citire()
{
  int i,x, y, j, c;

  fin>>n>>m;
  for(i=1; i<=m; i++)
   { fin>>x>>y>>c;
    a[x][y]=c;
   }
  for (i=1; i<=n; i++)
    for(j=1; j<=n; j++)
      if(a[i][j]==0) a[i][j]=infinit;
  fin.close();
}


void dijkstra()
 {
   int pas, mini, k, i;
   for(pas=1; pas<=n-1; pas++)
     {
       mini=infinit;
       for(i=1; i<=n; i++)
         if((viz[i]==0) && (d[i]<mini))
           { mini=d[i]; k=i; }
       viz[k]=1;
       for(i=1; i<=n; i++)
         if((viz[i]==0) && (d[k]+a[k][i]<d[i]))
           { d[i]=d[k]+a[k][i]; tata[i]=k; }
     }
 }

int main()
{ int i, s;
  citire();
  s=1;

  for(i=1; i<=n; i++)
    {
      viz[i]=0;
      d[i]=a[s][i];
      if(d[i]<infinit)
    tata[i]=s;
      else tata[i]=0;
    }
  viz[s]=1; tata[s]=0; d[s]=0;
  dijkstra();

  for(i=2; i<=n; i++)
    {
      fout<<d[i]<<' ';
    }

}