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

using namespace std;

#define NL "\n"
#define SPACE " "
#define INF INT_MAX

#define neighbor(p) p.first
#define cost(p) p.second

struct VertexContainer {
    int v;
    int *distance;

    VertexContainer(int v, int *d) {
        this->v = v;
        this->distance = d;
    }
};

struct MinHeap {
    // elementele propriu-zise din heap
    vector<VertexContainer> nodes;

    // pozitia fiecarui nod din graf in vectorul heapului, adica in nodes
    vector<int> pos;

    MinHeap(const int maxNodes) {
        // initial nu se afla niciun nod in heap
        pos = vector<int>(maxNodes, -1);
    }

    void push(VertexContainer data) {
        pos[data.v] = nodes.size();
        nodes.push_back(data);
        siftUp(data.v);
    }

    VertexContainer top() {
        return nodes.front();
    }

    void pop() {
        swap(pos[nodes.front().v], pos[nodes.back().v]);
        swap(nodes.front(), nodes.back());
        pos[nodes.back().v] = -1;
        nodes.pop_back();
        if (nodes.size() > 0)
            siftDown(nodes.front().v);
    }

    bool empty() const {
        return nodes.empty();
    }

    size_t size() const {
        return nodes.size();
    }

    void siftUp(const int node) {
        while (true) {
            int nodePos = pos[node];
            int parentPos = parent(nodePos);
            auto &data = nodes[nodePos];
            auto &parentData = nodes[parentPos];

            if (*(data.distance) < *(parentData.distance)) {
                swap(pos[data.v], pos[parentData.v]);
                swap(nodes[nodePos], nodes[parentPos]);
            } else {
                break;
            }
        }
    }

    void siftDown(const int node) {
        while (true) {
            size_t nodePos = pos[node];
            size_t leftPos = leftChild(nodePos);
            size_t rightPos = rightChild(nodePos);

            size_t smallestPos = nodePos;

            if (leftPos < nodes.size()
                    && *(nodes[leftPos].distance)
                        < *(nodes[smallestPos].distance))
                smallestPos = leftPos;

            if (rightPos < nodes.size()
                    && *(nodes[rightPos].distance)
                        < *(nodes[smallestPos].distance))
                smallestPos = rightPos;

            if (smallestPos == nodePos)
                break;

            swap(pos[node], pos[nodes[smallestPos].v]);
            swap(nodes[nodePos], nodes[smallestPos]);
        }
    }

    int parent(const int node) {
        if (node == 0)
            return 0;
        return (node - 1) >> 1;
    }

    int leftChild(const int node) {
        return (node << 1) + 1;
    }

    int rightChild(const int node) {
        return (node << 1) + 2;
    }
};

void dijkstra(list<pair<int, int>> *adj, const int n, ofstream &out) {
    vector<int> d(n, INF);

    d[0] = 0;

    MinHeap q(n);
    q.push(VertexContainer(0, &d[0]));

    while (!q.empty()) {
        int u = q.top().v;
        q.pop();

        for (auto &edge : adj[u]) {
            int v = neighbor(edge);
            int c = cost(edge);

            if (d[v] > d[u] + c) {
                bool unseenBefore = (d[v] == INF);
                d[v] = d[u] + c;

                if (unseenBefore) {
                    q.push(VertexContainer(v, &d[v]));
                } else {
                    q.siftUp(v);
                }
            }
        }
    }

    for (int i = 1; i <= n - 1; i++) {
        if (d[i] == INF)
            out << 0 << SPACE;
        else
            out << d[i] << SPACE;
    }
}

int main(void) {
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");

    int m, n;
    in >> n >> m;

    list<pair<int, int>> adj[n];

    int x, y, c;
    for (int i = 0; i < m; i++) {
        in >> x >> y >> c;
        adj[--x].push_back({--y, c});
    }

    dijkstra((list<pair<int, int>> *) adj, n, out);

    in.close();
    out.close();
    return 0;
}