#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
priority_queue <pii,vector<pii>,greater<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);
    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({cost,newnode});
                }
            }
        }
    }
    for(int i = 2; i <= N; ++i)
        cout << dp[i] << " ";
    return 0;
}