#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

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


int n;

struct edge {
    int y;
    int c;
};

struct edge_comp {
    bool operator()(const edge &e1, const edge &e2) {
        return e1.c > e2.c;
    }
};

int main() {
    int m;

    in >> n >> m;

    vector<vector<edge> > graph(n + 1);
    vector<int> d(n + 1, INT_MAX);
    priority_queue<edge, vector<edge>, edge_comp> pq;

    for (int i = 0; i < m; ++i) {
        int x, y, c;

        in >> x >> y >> c;

        edge e = {y, c};

        graph[x].push_back(e);
    }

    for (unsigned i = 0; i < graph[1].size(); ++i) {
        d[graph[1][i].y] = graph[1][i].c;

        pq.push(graph[1][i]);
    }

    while (!pq.empty()) {
        edge e = pq.top();

        pq.pop();

       // sel[e.y] = true;

        for (unsigned i = 0; i < graph[e.y].size(); ++i) {
            edge n = graph[e.y][i];

            if (d[n.y] > d[e.y] + n.c) {
                d[n.y] = d[e.y] + n.c;
                n.c = d[n.y];
                pq.push(n);
            }
        }
    }

    for (int i = 2; i <= n; ++i) out<<d[i]<<" " ;


    out << '\n';

    return 0;
}