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

#define LMAX 50010

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

int N, M;
vector<muchie> V[LMAX];
int C[LMAX];
queue<int> Q;
//int viz[LMAX];

void dijkstra() {
    int n, L=1;
    Q.push(1);

    for (int i=0; i<L; ++i) {
        n = Q.front();
        Q.pop();
        for (int j=0, e=V[n].size(); j<e; ++j) {
            muchie k = V[n][j];
            //--viz[k.nod];
            if (C[n] + k.cost < C[k.nod] || !C[k.nod]) {
                C[k.nod] = C[n] + k.cost;
                Q.push(k.nod);
                ++L;
            }

        }
    }
}

int main () {

    int x,y,c;

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

    scanf("%d %d", &N, &M);
    for (int i=0; i<M; ++i) {
        scanf("%d %d %d", &x, &y, &c);
        V[x].push_back(muchie(y,c));
//        ++viz[y];
    }

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