#include <cstdio>
#include <vector>
#define DIM 51000
#define INF ((1<<30)-1)
#define f first
#define s second
using namespace std;

FILE *fin = fopen("dijkstra.in" ,"r");
FILE *fout= fopen("dijkstra.out","w");

int N, M, Pos[DIM], Cost[DIM], X, Y, Z, K;
vector <int> V[DIM];
pair <int, int> Heap[DIM];

void SetUp(){
    fscanf(fin, "%d %d ", &N, &M);
    for(int i = 1; i <= M; i ++){
        fscanf(fin, "%d %d %d", &X, &Y, &Z);
        V[X].push_back(Y);
        V[X].push_back(Z);
    } K ++;
    Heap[K].f = 0; Heap[K].s = 1; Pos[K] = K;
    for(int i = 2; i <= N; i ++){
        K ++;
        Heap[K].f = INF;
        Heap[K].s = i;
        Pos[K] = K;
    }
    return;
}

void Shift(pair <int, int> Heap[], int Pos[], int poz, int N){
    if(poz != 1 && Heap[poz].f < Heap[poz/2].f){
        swap(Heap[poz], Heap[poz/2]);
        Pos[Heap[ poz ].s] = poz;
        Pos[Heap[poz/2].s] = poz/2;
        Shift(Heap, Pos, poz/2, N);
    }   return;
}

void Percolate(pair <int, int> Heap[], int Pos[], int poz, int N){
    int poz2 = poz * 2;
    if(poz2 + 1 <= N && Heap[poz2+1] < Heap[poz2])
        poz2 ++;
    if(poz2 <= N && Heap[poz] > Heap[poz2]){
        swap(Heap[poz], Heap[poz2]);
        Pos[Heap[poz ].s] = poz;
        Pos[Heap[poz2].s] = poz2;
        Percolate(Heap, Pos, poz2, N);
    }   return;
}

void Dijkstra(){
    while(K != 0){
        Cost[Heap[1].s] = Heap[1].f;
        for(int i = 0; i < V[Heap[1].s].size(); i += 2){
            int poz = Pos[V[Heap[1].s][i]], cost = V[Heap[1].s][i+1];
            if(Heap[poz].f > Heap[1].f + cost){
                Heap[poz].f = Heap[1].f + cost;
                Shift(Heap, Pos, poz, K);
            }
        }
        swap(Heap[1], Heap[K]);
        Pos[Heap[1].s] = 1;
        Pos[Heap[K].s] = K;
        K --;
        Percolate(Heap, Pos, 1, K);
    }
    return;
}

void Finish(){
    for(int i = 2; i <= N; i ++)
        fprintf(fout, "%d ", Cost[i]);
    return;
}

int main(){
    SetUp();
    Dijkstra();
    Finish();
    return 0;
}