#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
priority_queue <pii,vector<pii>,less<pii> > q;
int N,M;

int main() {
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    cin >> N >> M;
    vector<pii> a[N + 1];
    vector<bool> seen(N + 1,0);
    while(M--) {
        int x,y,c;
        cin >> x >> y >> c;
        a[x].push_back({c,y});
    }
    vector<int> dp(N + 1,(1 << 30));
    dp[1] = 0;
    q.push({0,1});
    while(!q.empty()) {
        while(!q.empty() && seen[q.top().second])
            q.pop();
        if(!q.empty()) {
            int node = q.top().second;
            seen[node] = 1;
            q.pop();
            for(auto i : a[node]) {
                int cost = i.first,newnode = i.second;
                if(dp[node] + cost < dp[newnode]) {
                    dp[newnode] = dp[node] + cost;
                    q.push({dp[newnode],newnode});
                }
            }
        }
    }
    for(int i = 2; i <= N; ++i){
        (dp[i] == (1 << 30) ? cout << 0 : cout << dp[i]);
        cout << " ";
    }
    return 0;
}