#include<fstream>
#define nmax 1<<16
#define inf 1<<30
#include<algorithm>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct NodGR
{
   int v,nod;
   struct NodGR* next;
};

typedef NodGR* NGR;

NGR a[nmax];

int h[nmax],pos[nmax],arb[nmax],s[nmax],viz[nmax],m,n,i,nrviz=1;

void write();
void read();
void adaug(int x,int y,int c);
void solve(int x);
void heap_down(int x);
void heap_up(int x);

int main()
{
   read();
   for (i=1;i<=n;++i)
      arb[i]=s[i]=inf;
   s[1]=0;
   for (i=1;i<=n;++i)
      h[i]=pos[i]=i;
   viz[1]=1;
   solve(1);
   write();
}

void read()
{
   int i,x,y,c;
   f>>n>>m;
   for (i=1;i<=m;++i)
   {
      f>>x>>y>>c;
      adaug(x,y,c);
   }
}

void adaug(int x,int y,int c)
{
   NGR p=new NodGR;
   p->v=c;
   p->nod=y;
   p->next=a[x];
   a[x]=p;
}

void solve(int x)
{
   NGR p;
   int val;
   for (p=a[x];p;p=p->next)
   {
      val=p->nod;
      if (!viz[val])
         if (s[x]+p->v<s[val])
         {
            s[val]=s[x]+p->v;
            arb[h[val]]=s[val];
            heap_up(h[val]);
         }
   }
   viz[pos[1]]=1;
   if (arb[1]!=inf)
   {
   arb[1]=inf;
   val=pos[1];
   heap_down(1);
   solve(val);
   }
}

void heap_down(int x)
{
   int posaux,valaux,t,f;
   valaux=arb[x];
   posaux=pos[x];
   t=x;
   f=x<<1;
   if (arb[f+1]<arb[f])
      ++f;
   while (valaux>arb[f]&&f<=n)
   {
      arb[t]=arb[f];
      pos[t]=pos[f];
      h[pos[t]]=t;
      t=f;
      f=f<<1;
      if (arb[f+1]<arb[f])
         ++f;
   }
   arb[t]=valaux;
   pos[t]=posaux;
   h[pos[t]]=t;
}

void heap_up(int x)
{
   int posaux,valaux,t,f;
   valaux=arb[x];
   posaux=pos[x];
   f=x;
   t=x>>1;
   while (t&&arb[t]>valaux)
      {
         arb[f]=arb[t];
         pos[f]=pos[t];
         h[pos[f]]=f;
         f=t;
         t=t>>1;
      }
   arb[f]=valaux;
   pos[f]=posaux;
   h[pos[f]]=f;
}

void write()
{
   int i;
   for (i=2;i<=n;++i)
      g<<(s[i]==inf?0:s[i])<<' ';
   g<<'\n';
}