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

typedef std::pair<int, int> edge;
/*
 * Comparator for the priority queue
 */
struct pq_cmp {
    bool operator()(edge a, edge b) {
        return a.second < b.second;
    }
};

std::vector<int> dijkstra(const std::vector<std::vector<edge> >& graph, const int source) {
    vector<int> dist(graph.size(), INT_MAX);
    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;
        pq.pop();

        // 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 < n; 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 < dist.size(); i++)
        printf("%d ", dist[i]);
    printf("\n");

    return 0;
}