#include <cstdio>
#include <vector>
using namespace std;

#define LMAX 50010
#define SWAP(a,b) aux=a, a=b, b=aux;
int aux;
const int INF = ~(1<<31);

struct muchie {
    int nod, cost;
    muchie () {nod=0, cost=0;}
    muchie (int n, int c) {
        nod = n;
        cost = c;
    }
};

int N, M, L;
vector<muchie> V[LMAX];
int heap[LMAX], C[LMAX];
int poz[LMAX];

int heap_pop () {
    int min = heap[1];
    SWAP(heap[1],heap[L]);
    poz[heap[1]] = 1;
    --L;

    int ch, p=1;
    while (p<=L) {
        ch = p;
        if ((p<<1)<=L) {
            ch = p<<1;
            if (ch+1<=L && C[heap[ch+1]]<C[heap[ch]])
             ++ch;
        } else break;

        if (C[heap[p]] > C[heap[ch]]) {
            poz[heap[ch]] = p;
            poz[heap[p]] = ch;
            SWAP(heap[p], heap[ch]);
            p = ch;
        } else break;
    }

    return min;
}

void upheap(int ch) {
    int p;
    while (ch>1) {
        p = ch>>1;
        if (C[heap[p]]>C[heap[ch]]) {
            poz[heap[ch]] = p;
            poz[heap[p]] = ch;
            SWAP(heap[p], heap[ch]);
            ch = p;
        } else break;
    }
}

void dijkstra() {
    for (int i=2; i<=N; ++i)
        C[i] = INF;

    int min;
    muchie k;
    poz[1] = 1;
    heap[++L] = 1;

    while (L) {
        min = heap_pop();
        for (int j=0, e=V[min].size(); j<e; ++j) {
            k = V[min][j];
            if (C[k.nod] > C[min] + k.cost) {
                C[k.nod] = C[min] + k.cost;

                if (poz[k.nod])
                    upheap(poz[k.nod]);
                else {
                    heap[++L] = k.nod;
                    poz[k.nod] = L;
                    upheap(L);
                }
            }
        }
    }
}

int main () {

    int x,y,c;

    freopen("dijkstra.in","rt",stdin);
    freopen("dijkstra.out","wt",stdout);

    scanf("%d %d", &N, &M);
    for (;M;--M) {
        scanf("%d %d %d", &x, &y, &c);
        V[x].push_back(muchie(y,c));
    }

    dijkstra();
    for (int i=2; i<=N; ++i)
        printf("%d ", (C[i]!=INF)? C[i]: 0);
    return 0;
}