#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;

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

int const maxsize = 50000;
int const INF = 1000000000;

int n, m;
int x, y, d;
int viz[maxsize];
int dist[maxsize];
vector<pair<int, int>> v[maxsize];

auto cmp = [](pair<int, int> a, pair<int, int> b) -> bool {
        return a.first > b.first;
    };
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);

int main() {

    in >> n >> m;
    for (int i = 1; i <= m; i++) {
        in >> x >> y >> d;
        v[x].push_back({y, d});
    }

    q.push({0, 1});
    for (int i = 2; i <= n; i++)
        dist[i] = INF;

    while (!q.empty()) {
        int node = q.top().second;
        viz[node]++;
        q.pop();
        for (int i = 0; i < v[node].size(); i++) {
            int neinode = v[node][i].first;
            int neidist = v[node][i].second;
            if(neidist + dist[node] < dist[neinode] && viz[neinode] == 0) {
                dist[neinode] = neidist + dist[node];
                q.push({dist[neinode], neinode});
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if(dist[i] == INF)
            out << 0 << " ";
        else
            out << dist[i] << " ";
    }
}