#include <fstream>
#include <queue>

using namespace std;

vector<int> cost;

struct Edge {
    int dest;
    int cost;
};

class Compare {
public:
    bool operator()(int &a, int &b) {
        return cost[a] > cost[b];
    }
};

int main() {
    int n, m;

    fstream f("dijkstra.in", ios::in);
    fstream g("dijkstra.out", ios::out);

    f >> n >> m;

    cost = vector<int>(n + 1, -1);
    vector<Edge> edges[n + 1];

    for(int i = 0; i < m; ++i) {
        int a, b, c;
        f >> a >> b >> c;
        edges[a].push_back(Edge{b, c});
    }

    cost[1] = 0;

    priority_queue<int, vector<int>,  Compare> nodeQueue;

    nodeQueue.push(1);
    while(!nodeQueue.empty()) {
        int currentNode = nodeQueue.top();

        for(Edge& edge : edges[currentNode]) {
            if(cost[edge.dest] == -1 || cost[currentNode] + edge.cost < cost[edge.dest]) {
                cost[edge.dest] = cost[currentNode] + edge.cost;
                nodeQueue.push(edge.dest);
            }
        }

        nodeQueue.pop();
    }

    for(int i = 2; i <= n; ++i) {
        g << cost[i] << ' ';
    }

    return 0;
}