#include <fstream>
#include <stdint.h>
#define nmax 50001
#define mmax 250001
using namespace std;
fstream f1("dijkstra.in", ios::in);
fstream f2("dijkstra.out", ios::out);
int32_t n, m, aux[nmax], cap[nmax];
const int32_t inf=900027001;
int32_t nrelh, sol[nmax];
///heapul va tine minte distantele de la nodul 1 la celelalte noduri nevizitate
///va fi un min heap
struct lista_ad
{
    int32_t vec, c;
} v[mmax];
struct heap
{
    int32_t nod, dist;
} h[nmax], vii;
struct muchii
{
    int32_t x, y, c;
} muc[mmax];
void citire()
{
    int32_t i;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>muc[i].x>>muc[i].y>>muc[i].c;
        aux[muc[i].x]++;
    }
    cap[1]=1;
    for(i=2; i<=n+1; i++)
    {
        cap[i]=aux[i-1]+cap[i-1];
        aux[i-1]=cap[i-1];
    }
    for(i=1; i<=m; i++)
    {
        v[aux[muc[i].x]].vec=muc[i].y;
        v[aux[muc[i].x]].c=muc[i].c;
        aux[muc[i].x]++;
    }
}
void init()
///initializezi heapul cu distantele actuale de la 1 la celelalte noduri
///1 -dist 0
///celelalte inf
{
    int32_t i;
    h[1].nod=1;
    h[1].dist=0;
    for(i=2; i<=n; i++)
    {
        h[i].nod=i;
        h[i].dist=inf;
    }
    nrelh=n;
}
void elimina_varf()
{
    h[1]=h[nrelh];
    nrelh--;
    vii=h[1];
    int32_t tata=1, fiu=tata*2;
    if((fiu+1<=nrelh)&&(h[fiu+1].dist < h[fiu].dist)) fiu++;

    while((fiu<=nrelh)&&(vii.dist> h[fiu].dist))
    {
        h[tata]=h[fiu];
        tata=fiu;
        fiu*=2;
        if((fiu+1<=nrelh)&&(h[fiu+1].dist < h[fiu].dist)) fiu++;
    }
    h[tata]=vii;
}
int32_t cauta_in_heap(int32_t nod)
{
    int32_t i;
    for(i=1; i<=nrelh; i++)
        if(h[i].nod==nod) return i;
    return (nrelh+1);///nu se gaseste in heap
}
void coboara_urca(int32_t indice)
{
    int32_t tata=indice, fiu=indice*2, mos;
    vii=h[indice];
    if((fiu+1<=nrelh)&&(h[fiu+1].dist < h[fiu].dist)) fiu++;

    while((fiu<=nrelh)&&(vii.dist> h[fiu].dist))
    {
        h[tata]=h[fiu];
        tata=fiu;
        fiu*=2;
        if((fiu+1<=nrelh)&&(h[fiu+1].dist < h[fiu].dist)) fiu++;
    }
     h[tata]=vii;

     mos=tata/2;
     ////vii memo nodul curent de comparat
     while((mos>=1)&&(h[mos].dist>vii.dist))
     {
         h[tata]=h[mos];
         tata=mos;
         mos/=2;
     }
     h[tata]=vii;
}
void dijkstra_cu_heap()
{
   int32_t j, vfmin, indice, valmin;
   while(nrelh>0)
   {
       vfmin=h[1].nod;
       valmin=h[1].dist;
       for(j=cap[vfmin]; j< cap[vfmin+1]; j++)
       {
           indice=cauta_in_heap(v[j].vec);///cauti un el din heap cu nodul v[j].vec
           if(indice<=nrelh)
           {
               if(h[indice].dist> valmin+v[j].c)
               {
                   h[indice].dist=valmin+v[j].c;
                   coboara_urca(indice);
               }
           }
       }
       sol[vfmin]=valmin;
       elimina_varf();
   }
}
void afisare()
{
    int32_t i;
    for(i=2; i<=n; i++)
    {
        if(sol[i]!=inf) f2<<sol[i]<<" ";
        else f2<<0<<" ";
    }
}
int main()
{
    citire();///+ creare lista de adiacenta
    init();
    dijkstra_cu_heap();
    afisare();
    return 0;
}