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

#define INT_N 50000

using namespace std;

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

const int INF = 1e9;

int n,m,x,y,c;
vector<pair<int,int>> adj[INT_N];
vector<int> dist(INT_N, INF);

void dijkstra(int nod){
    priority_queue<pair<int,int>, vector<pair<int,int>>, std::greater<pair<int,int>>> pq;
    pq.push(make_pair(0,nod));
    dist[nod] = 0;
    
    while(!pq.empty()){
        auto [wt,nodCrt] = pq.top();
        pq.pop();
        
        if(wt > dist[nodCrt])
            continue;
        
        for(auto edge: adj[nodCrt]){
            int vecin = edge.first;
            int cost = edge.second;

            if(dist[vecin] > dist[nodCrt] + cost){
                dist[vecin] = dist[nodCrt] + cost;
                pq.push(make_pair(dist[vecin], vecin));
            }
        }
    }

    
}

int main(){

    f >> n >> m;
    dist.resize(n+1,INF);
    adj->resize(n+1);
    for(int i=0; i<m; i++){
        f >> x >> y >> c;
        adj[x].push_back(make_pair(y,c));
    }

    dijkstra(1);

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

    return 0;
}