#include <bits/stdc++.h>

#define INF (1 << 30)

using namespace std;

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

struct Neighbour {
    int node, cost;
};

vector <vector <Neighbour>> G;
vector <int> C;

int n, m;

void Dijkstra(int start) {
    vector <bool> used(n + 1, false);
    C = vector <int> (n + 1, INF);

    priority_queue <int, vector <int>, greater <int>> pq;
    pq.push(start);
    C[start] = 0;
    used[start] = true;

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

        used[Node] = false;
        for(auto x : G[Node])
            if(C[x.node] > C[Node] + x.cost) {
                C[x.node] = C[Node] + x.cost;
                if(!used[x.node]) {
                    pq.push(x.node);
                    used[x.node] = true;
                }
            }
    }
}

int main() {
    fin >> n >> m;
    
    G.resize(n + 1);

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

    Dijkstra(1);

    for(int i = 2; i <= n; i ++)
        fout << (C[i] != INF ? C[i] : 0) << ' ';
    
    return 0;
}