#include<cstdio>
#include<algorithm>
using namespace std;

#define NMAX 50100
#define MMAX 250100
int val[2 * MMAX], nxt[2 * MMAX], last[NMAX], len[2 * MMAX];
int cnt = 0;

int add(int a, int b, int c){
    cnt++;
    val[cnt] = b;
    len[cnt] = c;
    nxt[cnt] = last[a];
    last[a] = cnt;
}


int heap[NMAX], hsize = 0, dist[NMAX], viz[NMAX];
const int INF = 2000000000;
void push_h(int x){
    if(hsize == 0){
        heap[1] = x;
        hsize = 1;
        return;
    }
    int cr = hsize + 1;
    hsize++;
    heap[cr] = x;
    while(dist[heap[cr]] < dist[heap[cr / 2]]){
        swap(heap[cr], heap[cr / 2]);
        cr = cr / 2;
    }
}

void pop_h(){
    swap(heap[1], heap[hsize]);
    heap[hsize] = 0;
    int cr = 1;
    while(1){
        if(dist[heap[cr]] > dist[heap[cr * 2]]){
            if(dist[heap[cr * 2]] > dist[heap[cr * 2 + 1]]){
                swap(heap[cr], heap[cr * 2  + 1]);
                cr = cr * 2 + 1;
            }
            else{
                swap(heap[cr], heap[cr * 2 ]);
                cr = cr * 2;
            }
        }
        else if(dist[heap[cr]] > dist[heap[cr * 2 + 1]]){
            swap(heap[cr], heap[cr * 2 + 1]);
            cr = cr * 2 + 1;
        }
        else{
            hsize--;
            break;
        }
    }
}

int top_h(){
    return heap[1];
}


int main(){
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int n, m, a, b, c;
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= n; i++)
        dist[i] = INF;
    dist[1] = 0;
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        //add(b, a, c);
    }
    push_h(1);
    while(hsize > 0){
        int k = top_h(), mch = last[k];
        viz[k] = 1;
        while(mch != 0){
            int u = val[mch], d = dist[k] + len[mch];
            if(d < dist[u] && !viz[u]){
                dist[u] = d;
                push_h(u);
            }
            mch = nxt[mch];
        }
        pop_h();
    }
    for(int i = 2; i <=n; i++){
        if(dist[i] == INF)
            printf("0 ");
        else
            printf("%d ", dist[i]);
    }
    return 0;
}