#include <stdio.h>
//#include<iostream.h>

#define maxn 50001
#define inf 100000
//const int maxn = 50001;
//const int inf = 1 << 30;

FILE *in = fopen("dijkstra.in","r"), *out = fopen("dijkstra.out","w");

struct graf
{
    int nod, cost;
    graf *next;
};

int n, m;
graf *a[maxn];
int d[maxn], h[maxn], poz[maxn], k;

void add(int where, int what, int cost)
{
    graf *q = new graf;
    q->nod = what;
    q->cost = cost;
    q->next = a[where];
    a[where] = q;
}

void read()
{
    fscanf(in, "%d %d", &n, &m);

    int x, y, z;
    for ( int i = 1; i <= m; ++i )
    {
        fscanf(in, "%d %d %d", &x, &y, &z);
        add(x, y, z);
    }
}

void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}

void upheap(int what)
{
  int tata;

  while (what>1)
  		{tata=what>>1;
          if( d[ h[tata] ]>d[ h[what] ]){ poz[h[tata]]=what;
          											poz[h[what]]=tata;
                                          swap(tata,what);
                                          what=tata;
          										 }
              else what=1;
      }
}

void downheap(int what)
{
    int f;
  while(what<=k)
  		{f=what;
         if((what<<1)<=k)
         	  {f=what<<1;
               if((f+1)<k)
                 if(d[ h[f+1] ]<d[ h[f] ])++f;
               }
          else return;
         if(d[ h[what] ]> d[ h[f] ]){ poz[ h[what] ]=f;
         									  poz[ h[f] ]=what;
                                      swap(what,f);
                                      what=f;
         									}
          else return;
        }

}

void dijkstra_heap()
{
int i, min;
graf *q;
for(i=2;i<=n;i++)
 poz[i]=-1,d[i]=inf;

h[++k]=1;
poz[1]=1;

while(k)
	{min=h[1];
    swap(1,k);
    poz[ h[1] ]=1;
    --k;
    downheap(1);

  q=a[min];
      while(q)
        { if(d[q->nod]>d[min]+q->cost)
             { d[q->nod]=d[min]+q->cost;
              if(poz[ q->nod ]!=-1)upheap(poz[q->nod]);
                else { h[++k]=q->nod;
                       poz[ h[k] ]=1;
                       upheap(k);
                     }
              }
           q=q->next;
        }
     }
}

int main()
{
    read();
    dijkstra_heap();

    for ( int i = 2; i <= n; ++i )
        fprintf(out, "%d ", d[i] == inf ? 0 : d[i]);
    fprintf(out, "\n");

    return 0;
}