#include <cstdio>
const int MAXN = 50001;
const int inf = 1 << 30;
struct graf{
    int nod;
    int cost;
    graf *next;
};

int n, m;
graf *a[MAXN];
int d[MAXN], h[MAXN], poz[MAXN], k;
using namespace std;

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 up(int x)
{
    int tata = x / 2;
    int nod = x;
    while(d[ h[tata] ] > d[ h[x] ] && tata > 1)
    {
        int aux = poz[ h[nod] ];
        poz[ h[nod] ] = poz[ h[tata] ];
        poz[ h[tata] ] = aux;
        aux = h[nod];
        h[nod] = h[tata];
        h[tata] = aux;
        nod = tata;
        tata = tata / 2;

    }

}
void down(int x)
{
    int nod = x;
    int fiust = nod * 2;
    int fiudr = nod * 2 + 1;
    while(fiudr <= k)
    {
        if(d[ h[nod] ] > d[ h[fiust] ] && d[ h[fiust] ] < d[ h[fiudr] ])
        {
            int aux = poz[ h[nod] ];
            poz[ h[nod] ] = poz[ h[fiust] ];
            poz[ h[fiust] ] = aux;
            aux = h[fiust];
            h[fiust] = h[nod];
            h[nod] = aux;
            nod = fiust;
            fiust = nod * 2;
            fiudr = nod * 2 + 1;
        }
        else
            if(d[ h[nod] ] > d[ h[fiudr] ] && d[ h[fiudr] ] < d[ h[fiust] ])
            {
                int aux = poz[ h[nod] ];
                poz[ h[nod] ] = poz[ h[fiudr] ];
                poz[ h[fiudr] ] = aux;
                aux = h[fiudr];
                h[fiudr] = h[nod];
                h[nod] = aux;
                nod = fiudr;
                fiust = nod * 2;
                fiudr = nod * 2 + 1;

            }
            else
            {
                return;
            }
    }
}
int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        scanf("%d %d %d", &x, &y, &cost);
        add(x, y, cost);
    }
    for(int i = 1; i <= n; i++)
    {
        d[i] = inf;
        poz[i] = -1;
    }
    poz[1] = 1;
    k = 0;
    h[++k] = 1;
    d[1] = 0;
    while(k)
    {
        int min = h[1];
        int aux = h[1];
        h[1] = h[k];
        h[k] = aux;
        poz[ h[1] ] = 1;
        --k;
        down(1);
        graf *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)
                {
                    up(poz[q->nod]);
                }
                else
                {
                    h[++k] = q->nod;
                    poz[ h[q->nod] ] = k;
                    up(k);
                }
            }
            q = q->next;

        }

    }
    for(int i = 2; i <= n; i++)
        printf("%d ", d[i]);
    return 0;
}