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

#include <fstream>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

#define N 100000

bool visited[N]; // not needed in heap implementation
int dist[N];

int n, m;
vector<pair<int, int>> adj_list[N];

void init_dist(int max_node) {
    for (int i = 1; i <= max_node; i++)
        dist[i] = INT_MAX;
}

void init_visited(int max_node) {
    for (int i = 1; i <= max_node; i++)
        visited[i] = false;
}

void dijkstra(int start_node) {

    init_dist(n);
    init_visited(n);

    /**
     * min-heap for storing vertices by distance to source node
     * in pairs (distance from node to source node, node_idx).
    */
    priority_queue<pair<int, int>, vector<pair<int, int>>, 
                    greater<pair<int, int>>> pq;
    
    pq.push(make_pair(0, start_node));
    dist[start_node] = 0;

    while (!pq.empty()) {
        
        // get node index with the shortest path to source node
        int node = pq.top().second;
        pq.pop();

        // update all nodes distances of the adjacent vertices of the
        // found vertex
        for (auto adj_node : adj_list[node]) {
            int idx = adj_node.first;
            int weight = adj_node.second;

            if (dist[idx] > dist[node] + weight) {

                dist[idx] = dist[node] + weight;
                pq.push(make_pair(dist[idx], idx));
            }
        }
    }

}

int main() {

    int s, x, y, c;

    in >> n >> m;

    s = 1;

    // scanf("%d %d %d", &n, &m, &s);

    for (int i = 1; i <= m; i++) {
        in >> x >> y >> c;
        // scanf("%d %d %d", &x, &y, &c);
        adj_list[x].push_back({y, c});
    }

    dijkstra(s);

    // change back to one
    for (int i = 2; i <= n; i++) {
        if (dist[i] != INT_MAX)
            out << dist[i] << " ";
            // printf("%d ", dist[i]);
        else {
            out << "0 ";
            // printf("NaN ");
        }
    }

    printf("\n");

    return 0;
}