#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <list>

void upheap(int node, std::vector<int> &pos, std::vector<int> &dist, std::vector<int> &myV) {
    if (!node) {
        return;
    }
    int parent = (node - 1) / 2;
    if (dist[myV[node]] < dist[myV[parent]]) {
        std::swap(pos[myV[node]], pos[myV[parent]]);
        std::swap(myV[node], myV[parent]);
        upheap(parent, pos, dist, myV);
    }
}

void downheap(int node, std::vector<int> &pos, std::vector<int> &dist, std::vector<int> &myV) {
    int left = 2 * node + 1;
    int right = left + 1;

    int curr = node;

    if (left < myV.size() && dist[myV[left]] < dist[myV[curr]]) {
        curr = left;
    }

    if (right < myV.size() && dist[myV[right]] < dist[myV[curr]]) {
        curr = right;
    }

    if (curr != node) {
        std::swap(pos[myV[node]], pos[myV[curr]]);
        std::swap(myV[node], myV[curr]);
        downheap(curr, pos, dist, myV);
    }
}

void pop(std::vector<int> &pos, std::vector<int> &dist, std::vector<int> &myV) {
    if (myV.size() == 1) {
        myV.pop_back();
        return;
    }
    std::swap(pos[myV[0]], pos[myV[myV.size() - 1]]);
    std::swap(myV[0], myV[myV.size() - 1]);
    myV.pop_back();
    downheap(0, pos, dist, myV);
}

struct Edge {
    int from, to, weight;
};

int main() {
    std::ifstream fileIn("dijkstra.in");
    std::ofstream fileOut("dijkstra.out");

    int nV, nM;

    fileIn >> nV >> nM;

    std::vector<std::list<Edge>> graph(nV + 1);
    std::vector<int> pos(nV + 1), dist(nV + 1, 2e9), myV(nV);

    dist[1] = 0;
    for (int i(0); i < nV; i++) {
        myV[i] = i + 1;
        pos[i + 1] = i;
    }

    Edge aux;
    for (int i(0); i < nM; i++) {
        aux = Edge();
        fileIn >> aux.from >> aux.to >> aux.weight;
        graph[aux.from].push_back(aux);
    }

    int node;
    while (!myV.empty()) {
        node = myV.front();
        pop(pos, dist, myV);
        for (Edge edge : graph[node]) {
            if (dist[edge.to] > dist[edge.from] + edge.weight) {
                dist[edge.to] = dist[edge.from] + edge.weight;
                upheap(pos[edge.to], pos, dist, myV);
            }
        }
    }

    for (int i(2); i <= nV; i++) {
        fileOut << dist[i] << ' ';
    }

    fileIn.close();
    fileOut.close();
    return 0;
}