#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int inf = 1e7 + 2;
struct Muchie {
    int x, y, c;
};
vector<Muchie> a[50002];
int n, m, p, q, i, x, y, c;
int d[50002];

static inline void Dijkastra(int nod = 1) {
    /// cost, nod
    set<pair<int, int>> q;
    q.insert({0, nod});

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

        for(auto vecin : a[nod]) {
            if(d[vecin.y] > d[nod] + vecin.c) {
                q.erase({d[vecin.y], vecin.y});

                d[vecin.y] = d[nod] + vecin.c;

                q.insert({d[vecin.y], vecin.y});
            }
        }
    }
}

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

    for(i = 1; i <= n; i++) d[i] = inf;
    
    Dijkastra();

    for(i = 2; i <= n; i++) {
        if(d[i] == inf) fout << "0 ";
        else fout << d[i] << " ";
    }

    return 0;
}