/*
    how about a coding trick?
*/
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define DIM 60000
#define INF ((1<<31)-1)
#define f first
#define s second
using namespace std;

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

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

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 = 1;
    Heap[1].f = 0; Heap[1].s = 1; Point[1] = 1;
    for(int i = 2; i <= N; i ++){
        K ++;
        Point[K] = i;
        Heap[K].f = INF;
        Heap[K].s = i;
    }
    return;
}

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

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

void Dijkstra(){
    int poz, poz2, cost;
    while(K != 0){
        poz = Heap[1].s;
        Cost[poz] = Heap[1].f;
        for(int i = 0; i < V[poz].size(); i += 2){
            poz2 = V[poz][i];
            cost = V[poz][i+1];
            if(Heap[Point[poz2]].f > Cost[poz] + cost){
                Heap[Point[poz2]].f = Cost[poz] + cost;
                Shift(Heap, Point, Point[poz2], K);
                Percolate(Heap, Point, Point[poz2], K);
            }
        }
        Point[Heap[1].s] = K;
        Heap[1].f = Heap[K].f; Heap[K].f = 0;
        Heap[1].s = Heap[K].s; Heap[K].s = 0;
        Point[Heap[1].s] = 1;
        K --;
        Percolate(Heap, Point, 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;
}