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

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

const int MAX_NUM = 50005;

int n, m;
vector<pair<int, int>> graph[MAX_NUM];
vector<int> d(MAX_NUM, INT_MAX);
vector<bool> visited(MAX_NUM, false);

int main() {
    fin >> n >> m;
    for (int  i = 0; i < m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        graph[a].push_back({b, c});
    }
    int s = 1;
    d[s] = 0;
    set<pair<int, int>> dist;
    dist.insert({0, s});
    while (!dist.empty()) {
        auto current = *dist.begin();
        int currentNode = current.second;
        dist.erase(dist.begin());
        for (auto edge : graph[currentNode]) {
            int node = edge.first, cost = edge.second;
            if (d[currentNode] + cost < d[node]) {
                d[node] = d[currentNode] + cost;
            }
            dist.insert({d[node], node});
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (d[i] == INT_MAX) {
            fout << "0 ";
        } else {
            fout << d[i] << " ";
        }
    }
    return 0;
}