#include<cstdio>
using namespace std;

const int nMax = 50000 + 5, mMax = 250000 + 5;
const int inf = 1 << 30;
int nod[mMax], urm[mMax], lst[nMax], val[mMax];
int d[nMax], pos[nMax], h[nMax];
int n,m, vf;

void change(int a, int b){
    int aux = h[a];
    h[a] = h[b];
    h[b] = aux;
    pos[h[a]] = a;
    pos[h[b]] = b;
}

void down(int p){
    int s = p << 1;
    if(s <= vf){
        if(s + 1 <= vf && d[h[s]] > d[h[s + 1]]) ++s;
        if(d[h[s]] < d[h[p]]){
            change(s, p);
            down(s);
        }
    }
}

void up(int p){
    int f = p >> 1;
    if(f && d[h[f]] > d[h[p]]){
        change(f, p);
        up(f);
    }
}

void add(int nod){
    h[++vf] = nod;
    pos[nod] = vf;
    up(vf);
}

int pop(){
    int nodC = h[1];
    change(1, vf);
    vf--;
    down(1);

    return nodC;
}

void dijkstra(){
    vf = 0;
    for(int i = 2 ; i <= n ; ++i) d[i] = inf;

    add(1);

    int nodC, nextPos, vec;
    while(vf){
        nodC = pop();

        nextPos = lst[nodC];
        while(nextPos){
            vec = nod[nextPos];

            if(d[vec] > d[nodC] + val[nextPos]){
                d[vec] = d[nodC] + val[nextPos];

                if(pos[vec]) up(pos[vec]);
                else add(vec);
            }

            nextPos = urm[nextPos];
        }
    }
}

int main (){
    FILE *in = fopen("dijkstra.in","r");
    FILE *out = fopen("dijkstra.out","w");

    fscanf(in,"%d%d", &n, &m);
    int a, b, c;
    for(int i = 1 ; i <= m ; ++i){
        fscanf(in, "%d%d%d", &a, &b, &c);

        //adauga in lista
        nod[++vf] = b;
        val[vf] = c;
        urm[vf] = lst[a];
        lst[a] = vf;
    }

    dijkstra();

    for(int i = 2 ; i <= n ; i++){
        d[i] = d[i] < inf ? d[i] : 0;
        fprintf(out,"%d ", d[i]);
    }
    return 0;
}