#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 5e4 + 5;
const int INF = 1e9;

int n;
int D[NMax];

vector < int > T;
vector < pair < int, int > > G[NMax];

inline bool cmp(const int &a, const int &b){
    return D[a] < D[b];
}

inline void Initialize(){
    for(int i = 2; i <= n; i++) D[i] = INF;
    T.push_back(1);
    make_heap(T.begin(), T.end(), cmp);
}

inline void Dijkstra(){
    Initialize();
    int node;
    while(!T.empty()){
        node = T.front();
        pop_heap(T.begin(), T.end(), cmp);
        T.pop_back();
        for(auto it: G[node]){
            if(D[it.first] > D[node] + it.second){
                D[it.first] = D[node] + it.second;
                T.push_back(it.first);
                push_heap(T.begin(), T.end(), cmp);
            }
        }
    }
}

int main(){
    int m, a, b, c;
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> a >> b >> c;
        G[a].push_back({b, c});
    }
    Dijkstra();
    for(int i = 2; i <= n; i++){
        fout << (D[i] < INF ? D[i] : -1) << " ";
    }
    return 0;
}