#include<fstream.h>
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define max 250003
struct muchie{long x,y,cost;}a[max];
long n,m,d[50003],dd[500][500];
int main()
{
 fin>>n>>m;
 long i,g,b,cc;
 for(i=1;i<=m;i++)
 {
  fin>>g>>b>>cc;
  a[i].x=g;
  a[i].y=b;
  a[i].cost=cc;
     if(g==1)
 // {
   d[b]=cc; //dd[b][1]=1;dd[b][2]=b;}
    }
 for(i=2;i<=n;i++)
  if(d[i]==0)
   d[i]=max;
 for(cc=1;cc==1;)
 {
  cc=0;
  for(i=1;i<=m;i++)
   if(d[a[i].y]>d[a[i].x]+a[i].cost)
   {
    d[a[i].y]=d[a[i].x]+a[i].cost;
    cc=1;
   }
 }
 for(i=2;i<=n;i++)
  if(d[i]==max)
   fout<<"0 ";
  else
   fout<<d[i]<<" ";
 fin.close();
 fout.close();
 return 0;
}