#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 0x7fffffff
#define NMAX (50000 + 3)
#define MMAX (100000 + 3)
using namespace std;

class Neighbor {
public:
    int index;
    int cost;

    Neighbor(int i, int c) : index(i), cost(c) {};
};

class Compare {
public:
    bool operator()(Neighbor a, Neighbor b) {
        return a.cost > b.cost;
    }
};

int main() {

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

    int n, m;

    vector<Neighbor> neighbors[NMAX];

    int distance[NMAX];
    bool visited[NMAX];

    int i, j;
    f >> n >> m;

    for (i = 1; i <= n; ++i) {
        distance[i] = INF;
        visited[i] = false;
    }

    for (; m; --m) {
        int x, y, c;

        f >> x >> y >> c;

        neighbors[x].push_back(Neighbor(y, c));
    }

    int source = 1;

    distance[source] = 0;
    priority_queue< Neighbor, vector<Neighbor>, Compare> unvisited;
    unvisited.push(Neighbor(source, 0));

    while (!unvisited.empty()) {
        Neighbor node = unvisited.top();
        unvisited.pop();
        if (!visited[node.index]) {
            for (const auto &neighbr : neighbors[node.index]) {
                if (distance[neighbr.index] == INF || distance[node.index] + neighbr.cost < distance[neighbr.index]) {
                    distance[neighbr.index] = distance[node.index] + neighbr.cost;
                    unvisited.push(Neighbor(neighbr.index, distance[neighbr.index]));
                }
            }
        }
        visited[node.index] = true;
    }

    for (i = 2; i <= n; ++i) {
        if (distance[i] != INF) {
            g << distance[i] << " ";
        } else {
            g << 0 << " ";
        }
    }

    return 0;
}