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

#define ll long long

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

vector<pair<int, int>> g[50005];

void dijkstra(int start, int n){
    set<pair<int, int>> s;

    vector<int> dist(n+1,INT_MAX);
    dist[start]=0;

    s.insert({0, start});

    while(!s.empty()){
        auto [d_currenta, u] = *s.begin();
        s.erase(s.begin());

        for(auto &[v, greutate] : g[u]){
            int d_new=d_currenta+greutate;

            if(d_new<dist[v]){
                //if(dist[v]!=INT_MAX)
                 //   s.erase(s.find({dist[v], v}));

                dist[v]=d_new;
                s.insert({dist[v],v});
            }
        }
    }

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

}

int main() {
    ios::sync_with_stdio(false);
    fin.tie(nullptr);

    int n; int m;
    fin>>n>>m;

    for(int i=1;i<=m;i++){
        int a, b, c;
        fin>>a>>b>>c;
        g[a].push_back({b,c});
    }

    dijkstra(1,n);

    return 0;
}