#include <stdio.h>
#include <vector>
#define NMAX 50005
#define INF (1<<31)-1
using namespace std;

vector< pair<int, int> > vf[NMAX];
int N, M, nrh, dist[NMAX], marked[NMAX], heap[NMAX], poz[NMAX], cost[NMAX];

void urca(int p){
    while(p > 1 && dist[heap[p]] < dist[heap[p/2]]){
        swap(heap[p], heap[p/2]);
        swap(poz[heap[p]],poz[heap[p/2]]);
        p /= 2;
    }
}

void insert_heap(int x){
    heap[++nrh] = x;
    poz[x] = nrh;
    urca(nrh);
}

void coboara(int p){
    int fs = 2 * p, fd = 2 * p + 1, bun = p;
    if(fs <= nrh && dist[heap[fs]] < dist[heap[bun]]){
        bun = fs;
    }
    if(fd <= nrh && dist[heap[fd]] < dist[heap[bun]]){
        bun = fd;
    }
    if(bun != p){
        swap(heap[p], heap[bun]);
        swap(poz[heap[p]], poz[heap[bun]]);
        coboara(bun);
    }
}

int get_min(){
    int m = heap[1];
    swap(heap[1], heap[nrh]);
    swap(poz[heap[1]], poz[heap[nrh]]);
    poz[m] = 0;
    nrh--;
    coboara(1);
    return m;
}

int main(){
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int i, j, x, y, c;
    scanf("%d%d", &N, &M);
    for(i = 1; i <= M; i++){
        scanf("%d%d%d", &x, &y, &c);
        vf[x].push_back(make_pair(y, c));
    }
    for(i = 2; i <= N; i++){
        dist[i] = INF;
    }
    dist[1] = 0;
    for(i = 1; i <= N; i++){
        insert_heap(i);
    }
    for(i = 1; i <= N; i++){
        x = get_min();
        marked[x] = true;
        for(j = 0; j < vf[x].size(); j++){
            y = vf[x][j].first;
            c = vf[x][j].second;
            if(!marked[y] && dist[y] > dist[x] + c){
                dist[y] = dist[x] + c;
                urca(poz[y]);
            }
        }
    }
    for(i = 2; i <= N; i++){
        printf("%d ", dist[i]);
    }
}