#include <bits/stdc++.h>

using namespace std;

const int N = 50010;

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

struct compare {
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) {
        return a.second > b.second;
    }
};

vector<pair<int, int>> v[N];
priority_queue<pair<int, int>, vector<pair<int, int>>, compare> heap;
int n, m, x, y, cost;

int dist[N], viz[N];



void dijkstra(int node) {
    viz[node] = 1;
    for (int i = 0; i < v[node].size(); i++) {
        if (viz[v[node][i].first] == 0)
            heap.push(make_pair(v[node][i].first, v[node][i].second + dist[node]));
        while (heap.size() != 0) {
            pair<int, int> top = heap.top();
            heap.pop();

            if (viz[top.first] == 0) {
                dist[top.first] = top.second;
                dijkstra(top.first);
            }
        }
    }
}

int main() {
    fin>>n>>m;
    for(int i=0;i<m;i++){
        fin>>x>>y>>cost;
        v[x].emplace_back(y, cost);
    }

    dijkstra(1);

    for(int i=2;i<=n;i++)
        fout<<dist[i]<<" ";

    return 0;
}