#include <bits/stdc++.h>

using namespace std;

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

int n , m ,d[50001],viz[50001];
vector <pair<int,int>> graf[50001];
priority_queue <pair<int,int>> pq;

void citire() {
    int x,y,c;
    fin >> n >> m;
    for (int i=1;i<=m;i++) {
        fin >> x >> y >> c;
        graf[x].push_back({y,c});
        //graf[y].push_back({x,c});
    }
    for (int i=2;i<=n;i++){
        d[i]=-1;
    }
}

int dijkstra(){
    pair<int,int> vf;
    int nod;
    nod=1;
    pq.push({0,1});
    d[1]=0;
    while (!pq.empty()){
        pq.pop();
        viz[nod]=1;
        for (pair<int,int> el: graf[nod]){
            if((d[nod]+el.second<d[el.first] || d[el.first]==-1) && viz[el.first]==0) {
                d[el.first]=d[nod]+el.second;
                pq.push({-d[el.first],el.first});
            }
        }
        if (viz[pq.top().second]==1) continue;
        nod=pq.top().second;
    }

}

int main(){
    citire();
    dijkstra();
    for (int i=2;i<=n;i++) fout << d[i] << " ";
}