#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 << 31 - 1;
int H[nmax], Pos[nmax], d[nmax], L ;

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

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

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

    while(p != y)
    {
        y = p;

        if((p<<1) <= L){
            if(d[H[y]] > d[H[p<<1]])
                y = p<<1;
        }
        else return;


        if((p << 1) + 1<= L)
            if(d[H[y]] > d[H[(p<<1) + 1]])
                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;
            p = y;
        }
    }
}

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

    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;
                if(Pos[p->info] != -1)
                    upheap(Pos[p->info]);
                else
                {
                    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;
}