#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, tata, aux, st, dr;

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

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

void downheap(int p)
{
    tata = p;
    do {
        p = tata;
        st = tata << 1;
        dr = st + 1;
        if(d[H[st]] < d[H[tata]] && st <= L)
            tata = st;

        if(d[H[dr]] < d[H[tata]] && dr <= L)
            tata = dr;

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

            Pos[H[p]] = p;
            Pos[H[tata]] = tata;
        }
    } while (p != tata);
}

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

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

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

        p = G[from];
        while ( p )
        {
            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 );
                }
            }

            p = p->next;
        }
    }

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

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