#include <fstream>
#include <vector>
#define NMAX 50001
#define MMAX 250001
#define INF 1000000000
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, p;
int cmin[NMAX], prec[NMAX];
bool z[NMAX];
struct vecin{ int v; int c; };
vector <vecin> G[NMAX];


void init();
void dijkstra(int);
void afisare();

int main(){
    init();
    dijkstra(1);
    afisare();
    return 0;
}

void init(){
    fin>>n>>m;

    int x, i; vecin aux;
    for(i = 1; i<=m; ++i){
        fin>>x>>aux.v>>aux.c;
        G[x].push_back(aux);
    }
}

void dijkstra(int vfs){
    //initializari
    int i;
    z[vfs] = 1;
    for(i = 1; i<=n; ++i){
        prec[i] = vfs;
        cmin[i] = INF;
    }
    prec[vfs] = 0; cmin[vfs] = 0;
    for(i = 0; i< G[vfs].size();++i) cmin[ G[vfs][i].v ] = G[vfs][i].c;

    int minim, vfmin, j;
    for(i =1 ; i<= n-1; ++i){
        minim = INF; vfmin = INF;
        for(j = 1; j<=n; ++j)
            if(minim > cmin[j] && !z[j]){
                minim = cmin[j];
                vfmin = j;
            }
        if(vfmin == INF) break;
        z[vfmin] = 1;
        for(j = 0; j< G[vfmin].size(); ++j){
            if(!z[ G[vfmin][j].v ] && cmin[ G[vfmin][j].v ] > cmin[vfmin] + G[vfmin][j].c){
               cmin[ G[vfmin][j].v ] = cmin[vfmin]+G[vfmin][j].c;
               prec[ G[vfmin][j].v ] = vfmin;
            }
        }
    }
}

void afisare(){
    int i;
    for(i = 2; i<=n; ++i){
        if(cmin[i] != INF)
            fout<<cmin[i]<<" ";
        else
            fout<<0<<" ";
    }
    fout<<'\n';
}