#include<fstream>
# define nmax 50002
# define mmax 250002
# define inf 2000000000
using namespace std;
struct muchie
{
  long x,y,c;
} G[mmax];
long D[nmax],M,N;
 long i,x,y,c,ok;
int main()
{


 ifstream f("dijkstra.in");
 ofstream g("dijkstra.out");
  f>>N>>M;
  for (i=1;i<=M;++i)
  {
   f>>x>>y>>c;
   G[i].x=x; G[i].y=y; G[i].c=c;
   if (x==1) D[y]=c;
  }
  for (i=2;i<=N;++i)
    if (D[i]==0) D[i]=inf;
  while(ok==0)
   {

     ok=1;
     for (i=1;i<=M;++i)
       if (D[G[i].y]>D[G[i].x]+G[i].c)
        {
                 D[G[i].y]=D[G[i].x]+G[i].c;
                  ok=0;
    }
  }
  for (i=2;i<=N;++i)
   if (D[i]!=inf)
   g<<D[i]<<" ";
         else g<<"0 ";
  return 0;
 }