#include <bits/stdc++.h>
#define INF INT_MAX
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct cv {
    int node;
    int cost;
    friend bool operator<(const cv& a, const cv& b) {
        return a.cost > b.cost;
    }
};

int n,m;

array<int,50001> ans;
array<vector<pair<int,int>>,50001> ad;
priority_queue<cv> pq;

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a,b,c;
        fin >> a >> b >> c;
        ad[a].push_back({b,c});
    }

    for (const auto& t : ad[1]) {
        pq.push({t.first,t.second});
    }

    ans[1] = -1;

    while (!pq.empty()) {
        const cv t = pq.top();
        pq.pop();
        if (!ans[t.node]) {
            ans[t.node] = t.cost;
            for (const auto& temp : ad[t.node]) {
                if (!ans[temp.first]) {
                    pq.push({temp.first, temp.second + t.cost});
                }
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        fout << ans[i] << ' ';
    }

    return 0;
}