#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int INF = (1 << 30);
const int MAX_NODES_COUNT = 50000 + 1;

int nodes_count, edges_count;

int minimum_cost[MAX_NODES_COUNT];
vector <int> graph[MAX_NODES_COUNT], cost[MAX_NODES_COUNT];
priority_queue < pair <int, int> > pq;

void read() {
    int node1, node2, current_cost;

    f >> nodes_count >> edges_count;
    for (int i = 1; i <= edges_count; i++) {
        f >> node1 >> node2 >> current_cost;
        graph[node1].push_back(node2);
        cost[node1].push_back(current_cost);
    }
}

void dijkstra(int source, int minimum_cost[]) {
    for (int i = 1; i <= nodes_count; i++)
        minimum_cost[i] = INF;

    minimum_cost[source] = 0;

    pair <int, int> p;
    int node, current_cost, new_cost, son, sons_count;

    p.first = 0;
    p.second = source;
    pq.push(p);

    while (!pq.empty()) {
        p = pq.top();
        pq.pop();

        node = p.second;
        current_cost = -p.first;

        sons_count = graph[node].size();

        for (int i = 0; i < sons_count; i++) {
            son = graph[node][i];
            new_cost = current_cost + cost[node][i];
            if (new_cost < minimum_cost[son]) {
                minimum_cost[son] = new_cost;
                p.first = -new_cost;
                p.second = son;
                pq.push(p);
            }
        }
    }
}

void write() {
    for (int i = 2; i <= nodes_count; i++) {
        if (minimum_cost[i] == INF)
            minimum_cost[i] = 0;
        g << minimum_cost[i] << ' ';
    }
    g << '\n';
}

int main() {
    read();
    dijkstra(1, minimum_cost);
    write();
    return 0;
}