#include <fstream>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int x[250001],y[25001],cost[25001],d[25001],n,m,infinit = 1000000001;
void citire()
 {

 cin>> n >>m;
 int i;
 for(i=1;i<=m;i++)
  {
  cin >>x[i]>>y[i]>> cost[i];
  if(x[i]==1)
    d[y[i]]=cost[i];
  }
 d[1]=0;
 for(i=2;i<=n;i++)
  d[i]=infinit;
 }
void dijkstra()
 {
 int ok=0;
 while(!ok)
  {
  ok=1;
  for(int i=1;i<=m;i++)
   if(d[y[i]]>d[x[i]]+cost[i])
    {
    d[y[i]]=d[x[i]]+cost[i];
    ok=0;
    }
  }
 }
void afisare()
 {
  for(int i=2;i<=n;i++)
  if(d[i]!=infinit)
  cout<<d[i]<<" ";
  else cout<<"0 ";
 }
int main()
 {
 citire();
 dijkstra();
 afisare();
 }