#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int INF = 1e9 + 7;
struct Muchie {
    int vec, cost;
};
int n, m, i, j, cost[50002], fr[50002];
vector<Muchie> gr[50002];

static inline void Dijkastra(int start = 1) {
    for(i = 1; i <= n; i++) cost[i] = INF;

    set<pair<int, int>> q;

    q.insert({0, start});
    cost[start] = 0;

    while(!q.empty()) {
        int nod = q.begin()->second;
        q.erase(q.begin());

        for(Muchie urm : gr[nod]) {
            if(cost[urm.vec] > cost[nod] + urm.cost) {
		q.erase({cost[urm.vec, urm.vec});
                cost[urm.vec] = cost[nod] + urm.cost;
                q.insert({cost[urm.vec], urm.vec});
            }
        }
    }
}

int main() {
    fin >> n >> m;
    for(i = 1; i <= m; i++) {
        int x, y, z;
        fin >> x >> y >> z;
        gr[x].push_back({y, z});
        //gr[y].push_back({x, z});
    }

    Dijkastra();
    for(i = 2; i <= n; i++) fout << cost[i] << " ";

    return 0;
}