#include <iostream>
#include <fstream>
#define inf 1000000000
#define dim 50002

using namespace std;

int h[dim], n, m, viz[dim], k;

struct graf{
    int vc, cost;
    graf *next;
} *L[250000];
int d[50005];


void add(graf *&prim, int vc, int c)
{
    graf *q= new graf;
    q -> vc = vc;
    q-> cost = c,
    q->next = prim;
    prim = q;
}

void down(int t)
{
    while(2*t <= k)
    {
        int c = 2*t;
        if(2*t+1 <=k && d[h[c]] >d[h[c+1]])
            c = c+1;
        if(d[h[t]] > d[h[c]])
        {
            int aux = h[t];
            h[t] = h[c];
            h[c] = aux;
        }
        t = c;
    }
}

void up(int c)
{
    int aux = d[h[c]], t=c/2;
    while(t >= 1 && aux<d[h[t]])
    {
        d[h[c]] = d[h[t]];
        c = t;
        t=t/2;
    }
    d[h[t]]= aux;
}

void creare()
{
    for(int i=n/2; i>0;i--)
        down(i);
}

void citire()
{
    freopen("dijkstra.in", "r", stdin);
    scanf("%d%d", &n, &m);

    for(int i=1;i<=n;i++)
    {
        d[i] = inf;
        h[i] = i;
    }
    d[1] = 0;
    for(int i = 1; i<=m; i++)
    {
        int a, b,c;
        scanf("%d%d%d", &a, &b,&c);
        add(L[a], b,  c);

    }
    for(graf*p = L[1]; p;p=p->next)
        d[p->vc] = p->cost;
    creare();
}

void sterg(int c)
{
    h[c] = h[k--];
    if( c>1 && d[h[c]] < d[h[c/2]])
        up(c);
    else
        down(c);
}



void lucru()
{
    k = n;
    viz[h[1]] = 1;
    sterg(1);
   while(k>0)
   {
       int vf = h[1];
       viz[h[1]] = 1;
       sterg(1);
       for(graf *p=L[vf];p;p=p->next)
            if(viz[p->vc] == 0 && d[p->vc]> d[vf] + p->cost)
            {
                d[p->vc]= d[vf] + p->cost;
            }
   }
   freopen("dijkstra.out", "w", stdout);
   for(int k=2;k<=n;k++)
   {
        printf("%d ",d[k]);
   }
}

int main()
{
    citire();
    lucru();
    return 0;
}