/// Craciun Catalin
///  Dijkstra
#include <iostream>
#include <fstream>

const int NMax = 200005;
const int inf = 1<<30;

using namespace std;

struct graf {

    int node;
    int cost;
    graf *previousNode;
};

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

int n,m;
graf *a[NMax];
int D[NMax], H[NMax], P[NMax], numberOfNodes = 0;

void upHeap (int k) {

    while (k/2 && D[H[k]] < D[H[k/2]]) {
        int aux = H[k];
        H[k] = H[k/2];
        H[k/2] = aux;

        P[H[k]] = k;
        P[H[k/2]] = k/2;

        k/=2;
    }
}

void downHeap (int x) {
    int aux, y=0;
    while (x!=y) {
        y = x;
        if (x*2 <= numberOfNodes && D[H[x]] < D[H[2*x]])
            y = 2*x;
        if (x*2+1 <= numberOfNodes && D[H[y]] < D[H[2*x+1]])
            y = 2*x+1;

        int aux = H[x];
        H[x] = H[y];
        H[y] = aux;

        P[H[x]] = x;
        P[H[y]] = y;

        x = y;
    }
}

void add (int where, int what, int cost) {

    graf *q = new graf;
    q->node = what;
    q->cost = cost;
    q->previousNode = a[where];
    a[where] = q;
}

void read() {

    f>>n>>m;
    for (int i=1;i<=m;i++) {
        int x, y, z;
        f>>x>>y>>z;
        add (x,y,z);
    }

    f.close();
}

void dijkstra_heap() {

    for (int i=2;i<=n;i++) {
        D[i] = inf;
        P[i] = -1;
    }

    P[1] = 1; H[++numberOfNodes] = 1;
    numberOfNodes = 1;

    while (numberOfNodes) {
        int minim = H[1];
        H[1] = H[numberOfNodes];
        P[1] = -1; P[H[1]] = 1;
        numberOfNodes--;

        downHeap(1);
        graf *q = a[minim];

        while (q) {
            if (D[q->node] > D[minim] + q->cost) {
                D[q->node] = D[minim] + q->cost;

                if (P[q->node] != -1) {
                    upHeap(P[q->node]);
                } else {
                    H[++numberOfNodes] = q->node;
                    P[H[numberOfNodes]] = numberOfNodes;
                    upHeap (numberOfNodes);
                }
            }
            q = q->previousNode;
        }
    }
}

int main() {

    read();
    dijkstra_heap();

    for (int i=2;i<=n;i++) {
        if (D[i] == inf)
            g<<0<<' ';
        else
            g<<D[i]<<' ';
    }

    return 0;
}