#include <fstream>
#include <iostream>
#define inf 1000000000
using namespace std;

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

struct muchie{
    int b, c;
    muchie *next;
};
muchie *G[50010];

int n, m, drum[50010], elemHeap, h[50010], poz[50010];

void Swap(int &a, int &b) {
    int aux = a;
    a = b;
    b = aux;
}

void sift(int h[], int n, int k) {
    int son;
    do {
        son = 0;
        if(2*k <= n) {
            son = 2*k;
            if(2*k+1 <= n && drum[h[2*k]] > drum[h[2*k+1]])
                son = 2*k +1;
            if(drum[h[son]] <= drum[h[k]])
                son = 0;
        }
        if(son) {
            Swap(poz[h[son]], poz[h[k]]);
            Swap(h[son], h[k]);
            k = son;
        }
    } while(son);
}

void percolate(int h[], int k) {
    int key = h[k];
    while(k > 1 && drum[key] < drum[h[k/2]]) {
        h[k] = h[k/2];
        poz[h[k]] = k;
        k /= 2;
    }
    h[k] = key;
    poz[h[k]] = k;
}

void heapAdd(int h[], int &n, int x) {
    h[++n] = x;
    poz[h[n]] = n;
    percolate(h, n);
}

void heapRemove(int h[], int &n, int k) {
    h[k] = h[n--];
    poz[h[k]] = k;
    sift(h, n, k);
}

void add(int i, int j, int c) {
    muchie *p = new muchie;
    p->b = j;
    p->c = c;
    p->next = G[i];
    G[i] = p;
}

int main() {
    f >> n >> m;

    for(int i = 1; i <= m; i++) {
        int a, b, c;
        f >> a >> b >> c;
        add(a, b, c);
    }

    for(int i = 2; i <= n; i++)
        drum[i] = inf, poz[i] = -1;
    poz[1] = 1;
    heapAdd(h, elemHeap, 1);

    while(elemHeap) {
        int minim = h[1];
        heapRemove(h, elemHeap, 1);

        for(muchie *p = G[minim]; p ; p = p->next) {
            if(drum[p->b] > drum[minim] + p->c) {
                drum[p->b] = drum[minim] + p->c;
                if(poz[p->b] != -1)
                    percolate(h, poz[p->b]);
                else
                    heapAdd(h, elemHeap, p->b);
            }
        }
    }

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