#include <fstream>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

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

const int INF = 1e9;
int N, M;

set<pair<int, int>> pq;

void Dijkstra(int sursa, vector<vector<pair<int, int>>> &edg, vector<int> &dist){
    dist[sursa] = 0;
    pq.insert({dist[sursa], sursa});

    vector<int> viz(N+1, 0);
    while(!pq.empty()){
        auto t=pq.begin();
        int nod = t->second;
        int cost = t->first;
        pq.erase(t);
        // if(viz[nod]) continue;
        //viz[nod] = 1;

        for(auto &v : edg[nod]){
            int w = v.second;
            int p = v.first;

            if(dist[p] > dist[nod] + w){
                pq.erase({dist[p], p}) ;
                dist[p] = dist[nod] + w;
                pq.insert({dist[p], p});

            }
        }
    }
}

int main(){
    fin>>N>>M;
    vector<vector<pair<int, int>>> edg;
    vector<int> dist(N+1, INF);
    edg.resize(N+1);
    while(M--){
        int u, v, w;
        fin>>u>>v>>w;
        edg[u].push_back({v, w});
    }
    Dijkstra(1, edg, dist);
    for(int i=2; i<=N; ++i){
        if(dist[i] == INF)
            fout<<0<<" ";
        else
            fout<<dist[i]<<" ";
    }
    return 0;
}