#include <queue>
#include <vector>
#include <cstdio>

#define DMAX 50010

using std::vector;
using std::priority_queue;

struct Arc {
    int node;
    int cost;
};

inline bool operator<(Arc x, Arc y) {
    return x.cost > y.cost;
}

int n, m;
vector<Arc> ad[DMAX];

int dp[DMAX];
bool onPQ[DMAX];
priority_queue< int, vector<int> > pq;

int main() {
    int a, b, c;
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    scanf("%d %d\n", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d\n", &a, &b, &c);
        ad[a].push_back({b, c});
    }

    pq.push(1);
    onPQ[1] = true;

    while (!pq.empty()) {
        int node = pq.top();
        pq.pop();
        onPQ[node] = false;

        for (Arc arc : ad[node])
            if (!dp[arc.node] || dp[node] + arc.cost < dp[arc.node]) {
                dp[arc.node] = dp[node] + arc.cost;
                if (!onPQ[arc.node]) {
                    pq.push(arc.node);
                    onPQ[arc.node] = true;
                }
            }
    }

    for (int i = 2; i <= n; i++)
        printf("%d ", dp[i]);
    printf("\n");

    fclose(stdout);
    return 0;
}