#include<fstream>
#include <iostream>
#include <queue>
#include<vector>

using namespace std;

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

int N, M;
vector<pair<int, int>> G[50005];
priority_queue<pair<int, int>>q;
vector<int> dist;
vector<int> vis;


void Dijkstra(int P){
    int k, i, cost;
    dist[P] = 0;
    q.push({0,P});
    while (!q.empty()){
        k = q.top().second;
        // cout<<k<<"\n";
        q.pop();
        // cout<<vis[k]<<"\n";
        if (vis[k] == 0){
            vis[k] = 1;
            for (auto e : G[k]){
                // cout<<e.second<<"\n";
                i = e.second;
                cost = e.first;
                if (dist[i] > dist[k]+cost){
                    dist[i] = dist[k]+cost;
                    q.push({dist[i], i});
                }
            }
        }
    }
}



int main() {
    fin >> N >> M;
    // cout<<N<<" "<<M<<endl;
    dist.assign(N+1, 1e9);
    vis.assign(N+1, 0);
    for (int i = 0; i < M; i++) {
        int u, v, w;
        fin >> u >> v >> w;
        G[u].push_back({w, v});
    }
    Dijkstra(1);
    for (int i=2;i<=N;i++) {
        fout<<dist[i]<<" ";
    }


    return 0;
}