#include<cstdio>
using namespace std;

const int nMax = 50000, mMax = 250000;
const int inf = 1 << 30;
int val[mMax], urm[mMax], cost[mMax], d[nMax], lst[nMax], h[nMax + 1], poz[nMax];
int n, m, k;

void change(int x, int y){
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;
}

void upH(int x){
    int f = x >> 1;

    while(f > 0 && d[h[f]] > d[h[x]]){
        poz[h[f]] = x;
        poz[h[x]] = f;
        change(f,x);
        x = f;
        f = x >> 1;
    }
}

void downH(int x){

 int f;
    while(x <= k){
        f = x << 1;
        if(f > k) return;
        if(f < k && d[h[f]] > d[h[f+1]]){
            f++;
        }
        if(d[h[x]] > d[h[f]]){
            poz[h[x]] = f;
            poz[h[f]] = x;
            change(f,x);
            x = f;
        }else return;
    }

}

void dijkstra(){
    for(int i = 1 ; i < n ; i++) d[i] = inf, poz[i] = -1;

    poz[0] = 1; k++;
    int pozUrm, vec, nodC;

    while(k){
        nodC = h[1];

        change(1,k); k--;
        poz[ h[1] ] = 1;

        downH(1);

        pozUrm = lst[nodC];
        while(pozUrm != -1){
            vec = val[pozUrm];

            if(d[vec] > d[nodC] + cost[pozUrm]){
                d[vec] = d[nodC] + cost[pozUrm];

                if(poz[vec] != -1){
                    upH(poz[vec]);
                }else{
                    h[++k] = vec;
                    poz[vec] = k;
                    upH(k);
                }
            }
             pozUrm = urm[pozUrm];
        }
    }

}

int main (){

    FILE *in = fopen("dijkstra.in","r");
    fscanf(in,"%d%d", &n, &m);

    for(int i = 0 ; i < n ; i ++) lst[i] = -1;

    for(int i = 0, x, y, ct; i < m ; i++){
        fscanf(in,"%d%d%d", &x, &y, &ct);
        val[i] = y - 1;
        urm[i] = lst[x - 1];
        cost[i] = ct;
        lst[x - 1] = i;
    }

    dijkstra();

    FILE *out = fopen("dijkstra.out","w");
    for(int i = 1 ; i < n ; i++){
        d[i] = d[i] < inf ? d[i] : 0;
        fprintf(out,"%d ", d[i]);
    }
    fprintf(out,"\n");
    return 0;
}