#include<stdio.h>
#include<vector>

using namespace std;

#define pb push_back
#define lg 50005
#define infinit 0x3f3f3f3f

int n, m, x, y, cst, i, nr[lg], val, nod, j, cnt[lg], car[lg], pz, nxt, tr[lg];

typedef pair<int, int> graf;
vector<graf> v[lg];
struct heap{
    int v, i;
};
heap hp[lg];

int gsnod(int i){
    if (i < n/2){
        if (hp[2*i].v < hp[2*i+1].v)
            return 2*i;
        return 2*i+1;
    }
    return 2*i;
}
void arj(int i){
    int nxt = gsnod(i), aux;

    if (i <= n/2)
        if (hp[i].v > hp[nxt].v){
            aux = hp[i].v, hp[i].v = hp[nxt].v, hp[nxt].v = aux;

            aux = hp[i].i, hp[i].i = hp[nxt].i, hp[nxt].i = aux;

            car[hp[i].i] = i, car[hp[nxt].i] = nxt;

            arj(nxt);
        }
}
void arj2(int i){
    int nxt = i/2, aux;

    if (i != 1)
        if (hp[i].v < hp[nxt].v){
            aux = hp[i].v, hp[i].v = hp[nxt].v, hp[nxt].v = aux;

            aux = hp[i].i, hp[i].i = hp[nxt].i, hp[nxt].i = aux;

            car[hp[i].i] = i, car[hp[nxt].i] = nxt;

            arj2(nxt);
        }
}
void citire(){
    int kkt = 0, j, nt;
    char sir[50];
    fgets(sir, 50, stdin), nt = 0;

    for (j = nt; sir[j] <= '9' && sir[j] >= '0'; j ++)
        kkt = kkt*10+sir[j]-'0';
    x = kkt, kkt = 0;
    nt = j+1;
    for (j = nt; sir[j] <= '9' && sir[j] >= '0'; j ++)
        kkt = kkt*10+sir[j]-'0';
    y = kkt, kkt = 0;
    nt = j+1;
    for (j = nt; sir[j] <= '9' && sir[j] >= '0'; j ++)
        kkt = kkt*10+sir[j]-'0';
    cst = kkt;
}
int main()
{
    freopen("dijkstra.in", "rt", stdin);
    freopen("dijkstra.out", "wt", stdout);

    scanf("%d%d\n", &n, &m);
    for (i = 1; i <= m; i ++){
        //scanf("%d%d%d", &x, &y, &cst);
        citire();

        nr[x] ++;
        v[x].pb(graf(y, cst));
    }

    for (i = 1; i <= n; i ++){
        hp[i].i = i;
        hp[i].v = infinit;
        car[i] = i;
    }

    hp[1].v = 0;
    for (i = 1; i <= n; i ++){
        val = hp[1].v;
        nod = hp[1].i;

        cnt[nod] = val;
        //fprintf(stderr, "am scos nodul %d cu costul %d\n", nod, val);

        hp[1].v = infinit+2;
        arj(1);
        tr[nod] = 1;

        for (j = 0; j < nr[nod]; j ++){
            nxt = v[nod][j].first;
            cst = v[nod][j].second;

            pz = car[nxt];
            //fprintf(stderr, "vecinul lui %d este %d cu costul %d ---> %d\n", nod, nxt, val+cst, hp[pz].i);
            if (val + cst < hp[pz].v && !tr[nxt]){
                hp[pz].v = val + cst;
                arj2(pz);
            }
        }
        //fprintf(stderr, "\n");
    }

    for (i = 2; i <= n; i ++){
        if (cnt[i] == infinit || cnt[i] == infinit+2)
            cnt[i] = 0;
        printf("%d ", cnt[i]);
    }
    printf("\n");

    return 0;
}