#include <bits/stdc++.h>

#define INF ((int)1e9)
#define NMAX ((int)5e4)

using namespace std;

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

struct edge {
    int dest, cost;
};

struct dist {
    int node, dist;
};

inline bool operator<(const dist& a, const dist& b) {
    if (a.dist == b.dist) {
        return a.node > b.node;
    }

    return a.dist > b.dist;
}

int n, m;
vector<edge> a[NMAX + 1];
int dist_vec[NMAX + 1];

void dijkstra() {
    priority_queue<dist> dist_pq;
    vector<bool> vis(n + 1, false);

    dist_vec[1] = 0;
    vis[1] = true;
    dist_pq.push({1, 0});
    for (int i = 2; i <= n; ++i) {
        dist_vec[i] = INF;
    }

    while (!dist_pq.empty()) {
        int node = dist_pq.top().node;
        dist_pq.pop();

        if (!node || dist_vec[node] == INF) {
            break;
        }

        for (auto it = a[node].begin(); it != a[node].end(); ++it) {
            edge next = *it;
            if (!vis[next.dest] && dist_vec[next.dest] > dist_vec[node] + next.cost) {
                dist_vec[next.dest] = dist_vec[node] + next.cost;
                dist_pq.push({next.dest, dist_vec[next.dest]});
            }
        }

        vis[node] = true;
    }
}

// void dijkstra() {
//     while (true) {
//         int node = (*dist_set.begin()).node;
//         if (!node || dist_vec[node] == INF) {
//             break;
//         }

//         // cout << "Set: ";
//         // for (auto it = dist_set.begin(); it != dist_set.end(); ++it) {
//         //     cout << (*it).node << " ";
//         // }
//         // cout << "\n";

//         for (auto it = a[node].begin(); it != a[node].end(); ++it) {
//             edge next = *it;
//             if (!vis[next.dest] && dist_vec[next.dest] > dist_vec[node] + next.cost) {
//                 dist_set.erase({next.dest, dist_vec[next.dest]});
//                 dist_vec[next.dest] = dist_vec[node] + next.cost;
//                 dist_set.insert({next.dest, dist_vec[next.dest]});
//             }
//         }

//         vis[node] = true;
//         dist_set.erase({node, dist_vec[node]});
//     }
// }

int main(void) {
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int src, dest, cost;
        fin >> src >> dest >> cost;

        a[src].push_back({dest, cost});
    }

    // cout << "sad\n";
    dijkstra();

    for (int i = 2; i <= n; ++i) {
        fout << ((dist_vec[i] == INF) ? 0 : dist_vec[i]) << " ";
    }

    fout << "\n";

    return 0;
}