#include <iostream>
#include <stdio.h>
#define nmax 50010

using namespace std;

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

nod *G[nmax];

void add(int from, int to, int tip){
    nod *p = new nod;
    p->info = to;
    p->cost = tip;
    p->next = G[from];
    G[from] = p;
}

int N, M;

void read()
{
    freopen ("dijkstra.in","r",stdin);
    freopen ("dijkstra.out","w",stdout);

    int i, a, b, c;
    scanf("%d %d",&N,&M);
    for(i = 1; i <= M; i++){
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
    }
}

const int inf = 1 << 30;
int H[nmax], Pos[nmax], d[nmax], L;

void upheap(int p)
{
    int aux;
    while((p>>1) && d[p] < d[p>>1])
    {
        aux = H[p];
        H[p] = H[p>>1];
        H[p>>1] = aux;

        Pos[H[p]] = p;
        Pos[H[p>>1]] = p >> 1;
    }
}

void downheap(int p)
{
    int y(0), aux;

    while(p != y)
    {
        y = p;
        if(d[y] > d[p>>1] && (p>>1) <= L)
            y = p>>1;
        if(d[y] > d[(p>>1) + 1] && (p>>1) + 1 <= L)
            y = (p>>1) + 1;

        if(y != p)
        {
            aux = H[p];
            H[p] = H[y];
            H[y] = aux;

            Pos[H[p]] = p;
            Pos[H[y]] = y;
        }
    }
}

void solve()
{
    int i, from;
    nod *p;
    for(i = 1; i <= N; i++)
        d[i] = inf;

    d[1] = 0;
    H[++L] = 1;
    Pos[1] = 1;

    while(L){
        from = H[1];
        H[1] = H[L--];
        Pos[H[1]] = 1;
        downheap(1);

        for(p = G[from]; p ; p = p->next)
            if(d[p->info] > d[from] + p->cost)
            {
                d[p->info] = d[from] + p->cost;
                H[++L] = p->info;
                Pos[p->info] = L;
                upheap(L);
            }
    }

    for(i = 2; i <= N; i++)
        if(d[i] == inf)
            printf("0 ");
        else printf("%d ",d[i]);
}

int main()
{
    read();
    solve();
    return 0;
}