#include<fstream>
#include<vector>
#define f first
#define s second
#define DIM 50005
#define INF 2000000000
using namespace std;
int n, m, i, x, y, z, nod, vecin;
int h[DIM], poz[DIM], sol[DIM], d[DIM], viz[DIM];
vector< pair<int, int> > v[DIM];
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
void upd(int pos){
    int c = pos, p = c / 2;
    while(p > 0 && d[ h[p] ] > d[ h[c] ]){
        swap(h[p], h[c]);
        poz[ h[p] ] = p;
        poz[ h[c] ] = c;
        c = p;
        p = c / 2;
    }
}
void elim(){
    int p = 1, c = 2;
    while(c <= n){
        if(c + 1 <= n && d[ h[c + 1] ] < d[ h[c] ]){
            c++;
        }
        if(d[ h[p] ] > d[ h[c] ]){
            swap(h[p], h[c]);
            poz[ h[p] ] = p;
            poz[ h[c] ] = c;
            p = c;
            c = p + p;
        }
        else{
            break;
        }
    }
}
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> x >> y >> z;
        v[x].push_back( make_pair(y, z) );
    }
    for(i = 1; i <= n; i++){
        h[i] = poz[i] = i;
        d[i] = INF;
    }
    d[1] = 0;
    while(d[ h[1] ] != INF){
        nod = h[1];
        sol[nod] = d[nod];
        viz[nod] = 1;
        for(i = 0; i < v[nod].size(); i++){
            vecin = v[nod][i].f;
            if(viz[vecin] == 0 && d[vecin] > d[nod] + v[nod][i].s){
                d[vecin] = d[nod] + v[nod][i].s;
                upd(poz[vecin]);
            }
        }
        d[nod] = INF;
        elim();
    }
    for(i = 2; i <= n; i++){
        fout<< sol[i] <<" ";
    }
    return 0;
}