#include <cstdio>
#include <vector>
#include <queue>
#include <limits.h>

#define N_MAX 50001

typedef struct {
    int dest, cost;
} EDGE;

struct distance {
    int node, distance;
    bool operator<(const struct distance& other) const {
        return distance > other.distance;
    }
} DISTANCE;

bool visited[N_MAX];
int N, M, dist[N_MAX];
std::vector<EDGE> graph[N_MAX];
std::priority_queue<struct distance> q;

struct distance _distance(int node, int distance) {
    struct distance d = {node, distance};
    return d;
}

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

    scanf("%d%d", &N, &M);
    for (int it = 0; it < M; ++it) {
        int start;
        EDGE edge;
        scanf("%d%d%d", &start, &edge.dest, &edge.cost);
        graph[start].push_back(edge);
    }
    
    for (int it = 1; it <= N; ++it) {
        dist[it] = INT_MAX;
        visited[it] = false;
    }

    dist[1] = 0;
    q.push(_distance(1, 0));
    while (!q.empty()) {
        while (visited[q.top().node]) q.pop();
        if (q.empty()) break;
        struct distance current = q.top();
        q.pop();
        visited[current.node] = true;
        for (int it = 0; it < graph[current.node].size(); ++it) {
            EDGE target = graph[current.node][it];
            if (!visited[target.dest] && current.distance + target.cost < dist[target.dest]) {
                dist[target.dest] = current.distance + target.cost;
                q.push(_distance(target.dest, dist[target.dest]));
            }
        }
    }

    for (int it = 2; it <= N; ++it) {
        printf("%d ", INT_MAX == dist[it] ? 0 : dist[it]);
    }

    return 0;
}