#include <iostream>
#include <fstream>
#include <vector>
#define nmax 101000
#define vmax 10000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <int> v[nmax],c[nmax];
int d[nmax], vis[nmax];

class Heap {
private:
    int a[3*nmax];
    int pos[3*nmax];
    int Size;
    bool hasParent(int nod) {
        return (nod != 1);
    }
    bool hasLeftChild(int nod) {
        return (2*nod <= Size);
    }
    bool hasRightChild(int nod) {
        return (2*nod + 1 <= Size);
    }
    int getRightChild(int nod ) {
        return (2*nod + 1);
    }
    int getLeftChild(int nod) {
        return (2*nod);
    }
    int getParent(int nod) {
        return (nod/2);
    }

    void HeapifyUp(int node) {
        bool canUp = true;
        while (hasParent(node) && canUp) {
            int parent = getParent(node);
            if (a[parent] > a[node] ) {
                swap(a[parent], a[node]);
                swap(pos[parent],pos[node]);
                node = parent;
            } else {
                canUp = false;
            }
        }
    }

    void HeapifyDown(int node) {
        bool canDown = true;
        while ( canDown ) {
            if (hasRightChild(node)) {

                int right = getRightChild(node);
                int left = getLeftChild(node);
                if (a[right] < a[left]) {
                    if (a[node] < a[right]) {
                        canDown = false;
                    } else {
                        swap(a[node], a[right]);
                        swap(pos[node], pos[right]);
                        node = right;
                    }
                } else {
                    if (a[node] < a[left]) {
                        canDown = false;
                    } else {
                        swap(a[node], a[left]);
                        swap(pos[node], pos[left]);
                        node = left;
                    }
                }

            } else {
                if (hasLeftChild(node)) {
                    int left = getLeftChild(node);
                    if (a[node] < a[left]) {
                        canDown = false;
                    } else {
                        swap(a[node], a[left]);
                        swap(pos[node], pos[left]);
                        node = left;
                    }

                } else {
                    canDown = false;
                }
            }
        }
    }

public:
    Heap() {
        Size = 0;
    }

    void add(int node, int cost) {
        Size ++;
        a[Size] = cost;
        pos[Size] = node;
        HeapifyUp(Size);
    }

    int getMinimumPosition() {
        return pos[1];
    }
    int getMinimumValue() {
        return a[1];
    }

    void deleteMinimum() {
        swap(a[1],a[Size]);
        swap(pos[1],pos[Size]);
        Size--;
        HeapifyDown(1);
    }


};

int main() {
    int n, p, m;
    f >> n >> m;
    p = 1;
    int x, y, cost;
    for (int i = 1;i <= m;i ++) {
   		f >> x >> y >> cost;
        v[x].push_back(y);
        c[x].push_back(cost);

    }
    for (int i = 1;i <= n;i ++) {
        d[i] = vmax;
    }
    for (int i = 0;i < v[p].size(); i ++) {
        x = v[p][i];
        cost = c[p][i];
        d[x] = cost;
    }
    d[p] = 0;
    vis[p] = 1;
    Heap h;
    for (int i = 1;i <= n;i ++) {
        if (vis[i] == 0) {
            h.add(i, d[i]);
        }
    }
    int nrMuchii = 0;
    for (int i = 1;nrMuchii < n - 1;i ++) {
        int nod = h.getMinimumPosition();
        int val = h.getMinimumValue();
        h.deleteMinimum();
        if (vis[nod] == 0) {
            nrMuchii ++;
            vis[nod] = 1;
            for (int j = 0;j < v[nod].size(); j ++) {
                int nCurr = v[nod][j];
                if (d[nCurr] > d[nod] + c[nod][j]) {
                    d[nCurr] = d[nod] + c[nod][j];
                    h.add(nCurr, d[nCurr]);

                }
            }
        }
    }
    for (int i = 2;i <= n;i ++) {
        if (d[i] == vmax) {
            g << "0 ";
        } else {
            g << d[i] << " ";
        }
    }

    return 0;
}