#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <limits>

using namespace std;

const int MAXN = 5e4;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

struct Graph{
    bitset<MAXN+1> v;
    vector<int> d;
    vector<pair<int, int>> e[MAXN+1];

};
Graph g;

struct comp{
    bool operator () (const int& a, const int& b){
        return g.d[a] > g.d[b];
    }
};
priority_queue<int, vector<int>, comp> pq;

void dijkstra(){

    while(!pq.empty()) {
        int cur = pq.top();
        pq.pop();

        if (g.v.test(cur)) continue;

        for (auto edge : g.e[cur]){
            int son = edge.first;
            int cost = edge.second;

            if (g.d[son] > g.d[cur] + cost) {
                pq.push(son);
                g.d[son] = g.d[cur] + cost;
            }
        }

        g.v.set(cur);

    }
}

int main() {
    int source = 0;

    int n, m;
    cin >> n >> m;

    while(m --){
        int u, v, cost;
        cin >> u >> v >> cost;
        g.e[u-1].push_back(make_pair(v-1, cost));

    }

    unsigned int maxx = 1 << 30;
    for(int i = 1; i <= n; ++i)
        g.d.push_back(maxx);

    g.d[source] = 0;
    pq.push(source);

    dijkstra();

    for (int i = 1; i < n; ++i) {
        (g.d[i] == maxx) ? (cout << 0) : (cout << g.d[i]);
        cout <<" ";
    }

    return 0;
}