#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], d[nmax];
const int32_t inf=900027001;
int16_t viz[nmax];
///d[i]= distanta minima de la nodul 1 la nodul i
struct lista_ad
{
    int32_t vec, c;
} v[mmax];
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()
///init vect d cu distantele actuale din lista de adiacenta de la noduri la nodul 1
{
    int32_t i;
    for(i=2; i<=n; i++)
        d[i]=inf;
    for(i=cap[1]; i<cap[2]; i++)
        d[v[i].vec]=v[i].c;
    viz[1]=1;
}
void dijkstra()
{
   int32_t i, j, vfmin, mini;
   for(i=1; i<n; i++)
   {
       ///selectezi nodul nevizitat, cu d minim
       mini=inf;
       vfmin=0;
       for(j=2; j<=n; j++)
           if((!viz[j])&&(mini> d[j])) {mini=d[j]; vfmin=j;}

       ///reactualizezi toate distantele de la 1 la nodurile nevizitate
       viz[vfmin]=1;
       for(j=cap[vfmin]; j< cap[vfmin+1]; j++)
           if((!viz[v[j].vec])&&(d[v[j].vec]> d[vfmin]+ v[j].c))
              d[v[j].vec]= d[vfmin]+ v[j].c;

   }
}
void afisare()
{
    int32_t i;
    for(i=2; i<=n; i++)
    {
       if(d[i]==inf) f2<<0<<" ";
       else f2<<d[i]<<" ";
    }
}
int main()
{
    citire();///+ creare lista de adiacenta
    init();
    dijkstra();
    afisare();
    return 0;
}