#include<bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

// void drum_critic() {
//     int n, m;
//     vector<vector<int>> adj(100005);
//     vector<int> d(2005,0);
//     vector<int> t(2005,0);
//     vector<pair<int,int>> ans(2005,{0,0});
//     vector<int> p(2005,-1);
//     int timp = 0;
//
//     fin >> n;
//     for (int i = 1 ; i <= n ; i ++) {
//         fin >> t[i];
//     }
//
//     fin >> m;
//     for (int i = 1; i <= m ; i++) {
//         int x,y;
//         fin >> x >> y;
//         adj[x].push_back(y);
//         d[y] ++;
//     }
//
//     queue<int> q;
//     for (int i = 1 ; i <= n ; i ++) {
//         if (!d[i]) {
//             q.push(i);
//         }
//     }
//
//     int maxi = 0;
//     int imax = 0;
//
//     while (!q.empty()) {
//         int node = q.front();
//         q.pop();
//         ans[node].second = ans[node].first + t[node];
//         timp = max(timp, ans[node].second);
//         if (ans[node].second > maxi) {
//             maxi = ans[node].second;
//             imax = node;
//         }
//         for (auto it : adj[node]) {
//
//             if (ans[node].second > ans[it].first) {
//                 ans[it].first = ans[node].second;
//                 p[it] = node;
//             }
//
//             d[it] --;
//             if (d[it] == 0) {
//                 q.push(it);
//             }
//
//         }
//     }
//
//     fout << "Timp minim " << timp << '\n';
//
//     stack<int> s;
//     while (imax != -1 ) {
//         s.push(imax);
//         imax = p[imax];
//     }
//
//     fout << "Activitati critice: ";
//     while (!s.empty()) {
//         fout << s.top() << " ";
//         s.pop();
//     }
//     fout << '\n';
//
//     for (int i = 1; i <= n ; i++) {
//         fout << i << ": " << ans[i].first << " " << ans[i].second << '\n';
//     }
//
//
// }

void diskstra1() {
    int n, m;
    vector<vector<pair<int,int>>> adj(250005);
    vector<int> vis(50005,0);
    //vector<int> p(50005,-1);
    vector<int> d(50005,INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    fin >> n >> m;

    for (int i = 1 ; i <= m ; i ++) {
        int x,y,c;
        fin >> x >> y >> c;
        adj[x].push_back({y,c});
        //adj[y].push_back({x,c});
    }

    // vector<int> pct_c;
    // int pct_n;
    // fin >> pct_n;
    // for (int i = 0 ; i < pct_n ; i ++) {
    //     int x;
    //     fin >> x;
    //     pct_c.push_back(x);
    // }

    int start = 1;
    //fin >> start;
    d[start] = 0;
    pq.push({0,start});

    while (!pq.empty()) {
        auto [cost,from] = pq.top();
        pq.pop();
        if (!vis[from]) {
            vis[from] = 1;
            for (auto it : adj[from]) {
                if (it.second + cost < d[it.first]) {
                    d[it.first] = it.second + cost;
                    pq.push({it.second + cost, it.first});
                }
            }
            //p[to] = from;
        }
    }
    for (int i = 2 ; i <= n; i++) {
        if (d[i] == INT_MAX ) {
            fout << 0 << " ";
        }else {
            fout << d[i] << " ";
        }
    }
}

int main() {
    diskstra1();
}