#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

set<pair<int, int>> cost;
vector<int> neighbors[50000];
int n, m, dis[5000][5000], shortest_path_to_node[50000];
int visited[50000], curr_node, a, b, c, min_val;

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        fin >> a >> b >> c;
        neighbors[a - 1].push_back(b - 1);
        dis[a - 1][b - 1] = c;
    }
    min_val = 20000;
    for (int i = 1; i < n; ++i) {
        shortest_path_to_node[i] = 20000;
    }
    while (!visited[curr_node]) {
        /*
        cout << "vis[]: ";
        for (int i = 0; i < n; ++i) {
            cout << visited[i] << ' ';
        }
        cout << endl;
        cout << "Current node " << curr_node + 1 << endl;
        */
        min_val = 20000;
        visited[curr_node] = 1;
        int node;
        int list_size = neighbors[curr_node].size();
        for (int i = 0; i < list_size; ++i) {
            int adj_node = neighbors[curr_node][i];
            if (!visited[adj_node]) {
                //cout << "Neighbor node " << adj_node + 1 << endl;
                int d = shortest_path_to_node[curr_node] + dis[curr_node][adj_node];
                //cout << "cal_dis = " << d << endl;
                //cout << "known_dis = " << shortest_path_to_node[adj_node] << endl;
                shortest_path_to_node[adj_node] = min(shortest_path_to_node[adj_node], d);
                //cout << "new_dis = " << shortest_path_to_node[adj_node] << endl;
                cost.insert({shortest_path_to_node[adj_node], adj_node});
            }
            //cout << endl;
        }
        /*
        for (auto i = cost.begin(); i != cost.end(); ++i) {
            cout << i->first << ' ' << i->second + 1 << endl;
        }
        */
        if (!cost.empty()) {
            curr_node = cost.begin()->second;
            cost.erase(cost.begin());
        }
        //cout << cost.begin()->first << ' ' << cost.begin()->second << endl << endl;
    }
    for (int i = 1; i < n; ++i) {
        fout << shortest_path_to_node[i] << ' ';
    }
    /*
    for (int i = 0; i < n; ++i) {
        int list_size = neighbors[i].size();
        cout << "node " << i + 1 << ": ";
        for (int j = 0; j < list_size; ++j) {
            cout << neighbors[i][j] + 1 << ' ';
        }
        cout << endl;
    }
    cout << endl;
    for (int i = 0; i < n; ++i) {
        int list_size = neighbors[i].size();
        for (int j = 0; j < list_size; ++j) {
            cout << "Distance(" << i + 1 << ',' << neighbors[i][j] + 1 << ") = " << dis[i][neighbors[i][j]] << endl;
        }
        cout << endl;
    }
    */
    return 0;
}