#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

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

const int INF = 1 << 30;
const int MAX_N = 50100;

int N, M;
vector<pair<int, int>> graph[MAX_N];
int cost[MAX_N];

void read_input(), print_output();
void dijkstra(int source);

int main() {
    read_input();
    dijkstra(1);
    print_output();
    return 0;
}

void read_input() {
    fin >> N >> M;
    for (int i = 1, a, b, c; i <= M; i += 1) {
        fin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
    }
}

void print_output() {
    for (int i = 2; i <= N; i += 1) {
        fout << (cost[i] == INF ? 0 : cost[i]) << ' ';
    }
}

void dijkstra(int source) {
    fill(cost, cost + N + 1, INF);
    vector<bool> visited(N + 1, 0);
    priority_queue<
        pair<int, int>,
        vector<pair<int, int>>,
        greater<pair<int, int>>
    > heap;

    heap.push(make_pair(0, source));
    cost[source] = 0;

    while (!heap.empty()) {
        int node = heap.top().second;
        heap.pop();

        if (visited[node]) continue;
        visited[node] = true;

        for (auto next: graph[node]) {
            if (cost[node] + next.second < cost[next.first]) {
                cost[next.first] = cost[node] + next.second;
                heap.push(make_pair(cost[next.first], next.first));
            }
        }
    }
}