#include <bits/stdc++.h>
using namespace std;
 
int n, m, d[50005];
const int INF = 2000000000;
vector <pair <int, int> > v[50005];
priority_queue <pair <int, int> > Heap;
inline void dijkstra(){
    d[1] = 0;
    d[0] = -1;
    Heap.push(make_pair(0, 1));
    pair <int, int> h;
    while(!Heap.empty()){
        h = Heap.top();
        Heap.pop();
        if(-h.first != d[h.second]) continue ;
        int nod = h.second;
        for(auto it : v[nod]){
            if(d[it.first] > d[nod] + it.second){
                d[it.first] = d[nod] + it.second;
                Heap.push(make_pair(-d[it.first], it.first));
            }
        }
    }
}
int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d%d", &n, &m);
    int x, y, c;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d%d", &x, &y, &c);
        v[x].push_back(make_pair(y, c));
    }
    for(int i = 2; i <= n ; ++i) d[i] = INF;
    dijkstra();
    for(int i = 2; i <= n ; ++i){
        if(d[i] == INF) d[i] = 0;
        printf("%d ", d[i]);
    }
    return 0;
}