#include <fstream>
#include <bits/stdc++.h>
using namespace std;

#define INF 1<<30

int main(){
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int n, m, a, b, c;
    fin>>n>>m;
    vector<vector<pair<int, int>>> v(n+1);
    for(int i = 0; i < m; i++){
        fin>>a>>b>>c;
        v[a].push_back({c, b});
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;    
    vector<int> dist(n+1, INF);
    dist[1] = 0;
    int d, node, val, next;
    pq.push({0, 1});
    while(!pq.empty()){
        d = pq.top().first, node = pq.top().second;
        pq.pop();
        if(d > dist[node])
            continue;
        for(auto h : v[node]){
            val = h.first, next = h.second;
            if(dist[node] + val < dist[next]){
                dist[next] = dist[node] + val;
                pq.push({dist[next], next});
            }
        }
    }

    for(int i = 2; i <= n; i++){
        if(dist[i] == INF)
            fout<<"0 ";
        else fout<<dist[i]<<" ";
    }

    return 0;
}