#include <bits/stdc++.h>

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

int main(){
    int n,m;
    if(!(fin>>n>>m)) return 0;
    std::vector<std::vector<std::pair<int,int>>> L(n+1);
    for(int i=0;i<m;i++){
        int n1,n2,w;
        fin>>n1>>n2>>w;
        L[n1].push_back({n2,w});
    }

    const long long INF = INT_MAX;
    std::vector<long long> dist(n+1, INF);
    std::vector<char> vis(n+1, 0);

    dist[1] = 0;
    std::priority_queue<std::pair<long long,int>,
                        std::vector<std::pair<long long,int>>,
                        std::greater<std::pair<long long,int>>> pq;
    pq.push({0, 1});
    
    while(!pq.empty()){
        auto [d,u] = pq.top(); pq.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto &e : L[u]){
            int v = e.first;
            int w = e.second;
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    for(int i=2;i<=n;i++){
        if(dist[i]==INF) fout << 0;
        else fout << dist[i];
        if(i<n) fout << ' ';
    }
    fin.close();
    fout.close();
    return 0;
}