/*
 * https://www.infoarena.ro/problema/dijkstra
 */

#include <bits/stdc++.h>

using namespace std;

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

int V, E, s;
vector<vector<pair<int, int>>> adjList;
vector<int> dist, parrent;

void init(){
    s = 1;
    adjList.resize(V+1);
    dist.resize(V+1, INT_MAX);
    parrent.resize(V+1);
    dist[s] = parrent[s] = 0;
}
void read(){
    in >> V >> E;
    init();
    for(int i = 1; i <= E; i++){
        int u, v, w;
        in >> u >> v >> w;
        adjList[u].emplace_back(v, w);
    }
}

void dijkstra(){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<> > q;
    q.push({dist[s], s});
    while(!q.empty()){
        int u = q.top().second;
        q.pop();
        for(auto edge: adjList[u]){
            int v, w;
            v = edge.first;
            w = edge.second;
            if(dist[u]+w < dist[v]){
                dist[v] = dist[u]+w;
                parrent[v] = u;
                q.push({dist[v], v});
            }
        }
    }
}

void print(){
    for(int u = 1; u <= V; u++){
        cout << u <<  ": ";
        for(auto edge: adjList[u]) {
            int v, w;
            v = edge.first;
            w = edge.second;
            cout << "{" << v << ", " << w << "} ";
        }
        cout << endl;
    }
}

int main() {
    read();
    dijkstra();
    for(int i = 2; i <= V; ++i)
        out << dist[i] << ' ';

    return 0;
}