#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(1, 0));
    pair <int, int> h;
    while(!Heap.empty()){
        h = Heap.top();
        Heap.pop();
        int nod = h.first;
        for(auto it : v[nod]){
            if(d[it.first] > d[nod] + it.second){
                d[it.first] = d[nod] + it.second;
                Heap.push(make_pair(it.first, -d[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)
        printf("%d ", d[i]);
    return 0;
}