#include <fstream>
#include <queue>

using namespace std;

const int MAX_N = 50000;
const int MAX_M = 250000;
const int MAX_WEIGHT = 20000;
const int NIL = -1;

struct Arc {
    int v, weight;
    int next;
};

Arc G[MAX_M];
int head[MAX_N];

int D[MAX_N];

queue <int> Q[MAX_WEIGHT];

void addArc(int u, int v, int weight, int pos) {
    G[pos].v = v;
    G[pos].weight = weight;
    G[pos].next = head[u];
    head[u] = pos;
}

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin.tie(0);
    ios_base::sync_with_stdio(false);

    int N, M; fin >> N >> M;

    for (int i = 0; i < N; ++ i) {
        head[i] = NIL;
    }
    for (int i = 0; i < M; ++ i) {
        int u, v, weight; fin >> u >> v >> weight;
        addArc(u - 1, v - 1, weight, i);
    }

    for (int i = 1; i < N; ++ i) {
        D[i] = MAX_WEIGHT - 1;
        Q[MAX_WEIGHT - 1].push(i);
    }

    D[0] = 0;
    Q[0].push(0);

    for (int i = 0; i < MAX_WEIGHT; ++ i) {
        while (!Q[i].empty()) {
            int u = Q[i].front();
            Q[i].pop();

            if (D[u] == i) {
                for (int j = head[u]; j != NIL; j = G[j].next) {
                    int v = G[j].v;

                    if (D[v] > D[u] + G[j].weight) {
                        D[v] = D[u] + G[j].weight;
                        Q[D[v]].push(v);
                    }
                }
            }
        }
    }

    for (int i = 1; i < N; ++ i) {
        fout << ((D[i] == MAX_WEIGHT - 1) ? 0 : D[i]) << " \n"[i == N - 1];
    }
    fout.close();
    return 0;
}