#include <stdio.h>
#include <algorithm>

using namespace std;
struct nod {int val,pr;nod *urm;};
nod *v[50002];
int h[50002],d[50002],pos[50002],n,n1,cur,m,x,y,pr,i;
FILE *f,*g;

void swap (int i,int j)
{
    int aux;
    aux=h[i];
    h[i]=h[j];
    h[j]=aux;

    pos[h[j]]=j;
    pos[h[i]]=i;

}
void upheap (int k)
{   int t;
    if (k>=1)
    {
        t=k/2;
        if (d[h[k]]<d[h[t]])
        {
            swap (k,t);
            upheap (t);
        }
    }
}
void dwheap (int k,int n)
{   int st=0,dr=0;
    st=k*2;
    if (st<=n)
    {
        dr=k*2+1;
        if (d[h[dr]]<d[h[st]] && dr<=n) st=dr;


        if ( d[h[st]]<d[h[k]])
        {
            swap (st,k);
            dwheap (st,n);
        }

    }
}
void buildheap (int k)
{
    for (i=1;i<=k;i++) upheap (i);
}
void add (int x,int y)
{
    nod *t;
    t=new nod;
    t->val=y;
    t->pr=pr;
    t->urm=v[x];
    v[x]=t;
}
void scot ()
{
    swap (1,n);
    n--;
    dwheap (1,n);

}
int main()
{f=fopen ("dijkstra.in","r");
 g=fopen ("dijkstra.out","w");
 fscanf (f,"%d%d",&n,&m);
 n1=n;
 for (i=1;i<=m;i++)
 {
     fscanf (f,"%d%d%d",&x,&y,&pr);
     add (x,y);
 }
 for (i=1;i<=n;i++)
 {
     d[i]=0x3f3f3f;
     pos[i]=i;
     h[i]=i;
 }
 d[1]=0;
 buildheap (n);
 nod *t;
 while (n>=1)
 {
     scot ();
     cur=h[n+1];
     for (t=v[cur];t;t=t->urm)
     {
         if (d[t->val]>d[cur]+t->pr)
         {
             d[t->val]=d[cur]+t->pr;
             upheap (pos[t->val]);
         }
     }
 }
 for (i=2;i<=n1;i++)
  {
        if (d[i]<0x3f3f3f) fprintf (g,"%d ",d[i]);
              else fprintf (g,"0 ");
  }


    return 0;
}