#include <fstream>
#define NMAX 50002
#define INFINIT 999999999
#include <vector>
#include <queue>
#include <functional>

using namespace std;

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

struct varf{
    int x;
    int c;
    friend bool operator >(varf, varf);
};
bool operator >(varf a, varf b){
    return a.c > b.c;
}

int n, start;
vector<varf> G[NMAX];
bool uz[NMAX];
int cmin[NMAX];
int prec[NMAX];

priority_queue<varf, vector<varf>, greater<varf> > H;

void citire();
void dijkstra();
void afisare();

int main(){
    citire();
    dijkstra();
    afisare();
    fin.close();
    fout.close();
    return 0;
}

void citire(){
    varf aux;
    int i, a, m;
    fin >> n >> m;
    start = 1;
    for(i=1; i<=m; i++){
        fin >> a >> aux.x >> aux.c;
        G[a].push_back(aux);
        }
    uz[start] = 1;
    for(i=1; i<=n; i++){
        cmin[i] = INFINIT;
        prec[i] = start;
        }
    cmin[start] = 0; prec[start] = 0;
    for(i=0; i<G[start].size(); i++){
        H.push(G[start][i]);
        cmin[G[start][i].x] = G[start][i].c;
        prec[G[start][i].x] = start;
        }
}

void dijkstra(){
    varf aux, alta;
    int i, nr;
    nr = 1;
    while(nr < n && !H.empty()){
        aux = H.top();
        H.pop();
        if(!uz[aux.x]){
            uz[aux.x] = 1;
            nr++;
            for(i=0; i<G[aux.x].size(); i++)
                if(cmin[aux.x] + G[aux.x][i].c < cmin[G[aux.x][i].x] && !uz[G[aux.x][i].x]){
                    cmin[G[aux.x][i].x] = cmin[aux.x] + G[aux.x][i].c;
                    prec[G[aux.x][i].x] = aux.x;
                    alta.x =  G[aux.x][i].x;
                    alta.c = cmin[G[aux.x][i].x];
                    H.push(alta);
                    }
            }
        }
}

void afisare(){
    int i;
    for(i=2; i<=n; i++)
        fout << cmin[i] << ' ';
    fout << '\n';
    /*for(i=0; i<n; i++)
        fout << prec[i] << ' ';
    fout << '\n';*/
}