#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 / 2;

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

void downH(int x){

    int ok = 1, al;
    while(x < k && ok){
        ok = 0;
        al = h[x];
        if(x * 2 <= k && al > h[x * 2]){
            ok = 1;
            al = h[x * 2];
        }
        if(x * 2 + 1 <= k && al > h[x * 2 + 1]){
            ok = 2;
            al = h[x * 2 + 1];
        }

        if(ok == 1){
            poz[ h[ x * 2 ] ] = x;
            poz[ h[ x ] ] = x * 2;
            change(x, x+ 2);
        }else if (ok == 2){
            poz[ h[ x * 2 + 1] ] = x;
            poz[ h[ x ] ] = x * 2 + 1;
            change(x, x * 2 + 1);
        }
    }

}

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

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


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

        change(1,k); k--;
        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++)
        fprintf(out,"%d ", d[i]);
    fprintf(out,"\n");
    return 0;
}