#include <bits/stdc++.h>
#define fi first 
#define se second
#define int long long
using namespace std;

void dijkstra(int st, vector<vector<pair<int, int>>> &a, vector<int> &d) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({1, st});
    while(pq.size()) {
        int dis = pq.top().fi;
        int pos = pq.top().se;
        pq.pop();

        if(d[pos])
            continue;
        d[pos] = dis;
        
        for(auto i : a[pos]) {
            pq.push({dis + i.se, i.fi});
        }
    }
}

signed main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m; cin >> n >> m;

    vector<vector<pair<int, int>>> a(n + 1);

    for(int i = 1; i <= m; i ++) {
        int x, y, z; cin >> x >> y >> z;
        a[x].push_back({y, z});
    }

    vector<int> d(n + 1);
    
    dijkstra(1, a, d);

    for(int i = 2; i <= n; i ++) {
        cout << d[i] - 1 << ' ';
    }
}