#include<bits/stdc++.h>
using namespace std;

typedef std::pair<int, int> edge;
vector<int> dist(50009, INT_MAX);
/*
 * Comparator for the priority queue
 */
struct pq_cmp {
    bool operator()(edge a, edge b) {
        return dist[a.first] < dist[b.first];
    }
};
std::vector<int> dijkstra(const std::vector<std::vector<edge> >& graph, const int source) {
    priority_queue<edge, vector<edge>, pq_cmp> pq;
    pq.push(make_pair(source, 0));  // add source to the priority queue
    dist[source] = 0;  // make the distance to source 0
    while(!pq.empty()) {
        // get the first node in queue and remove it
        int current = pq.top().first;
        int w = pq.top().second;
        pq.pop();
        if(dist[current] < w) continue;
        // loop through its neighbors to recalculate the distances
        for(int i = 0; i < graph[current].size(); i++) {
            int neighbor = graph[current][i].first;

            int weight = graph[current][i].second;
            // if we found a better distance, update it and add the node in the queue
            if (dist[neighbor] > dist[current] + weight) {
                dist[neighbor] = dist[current] + weight;
                pq.push(make_pair(neighbor, dist[neighbor]));
            }
        }
    }

    return dist;
}

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

    int n, m, src, dst, weight;
    scanf("%d%d", &n, &m);

    std::vector<std::vector<edge> > graph(n);

    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &src, &dst, &weight);
        graph[src - 1].push_back(make_pair(dst - 1, weight));
    }
    vector<int> dist;
    dist = dijkstra(graph, 0);

    for(int i = 1; i < n; i++) {
        if(dist[i] == INT_MAX)
            printf("0 ");
        else printf("%d ", dist[i]);
    }

    return 0;
}