#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int const maxim=50005;
int const oo = (1 << 30)-1;
int n,m;
int D[maxim];
bool inCoada[maxim];
vector <pair <int,int>>G[maxim];

struct compara{
bool operator()(int x, int y){
    return D[x]>D[y];
}
};
priority_queue < int , vector <int>, compara > coada;

void citire(){
in >> n >> m;
for(int i=0;i<m;i++){
    int x,y,c;
    in >> x >> y >> c;
    G[x].push_back(make_pair(y,c));
    }
}

void dijkstra(int nodstart){
for(int i=1;i<=n;i++)D[i]=oo;
D[nodstart]=0;
coada.push(nodstart);
inCoada[nodstart]=true;
while(!coada.empty()){
    int nodcurent=coada.top();
    coada.pop();
    inCoada[nodcurent]=false;
    for(unsigned int i=0;i<G[nodcurent].size();i++){
        int Vecin = G[nodcurent][i].first;
        int Cost = G[nodcurent][i].second;
        if(D[nodcurent]+Cost < D[Vecin]){
            D[Vecin]=D[nodcurent]+Cost;
            if(inCoada[Vecin]==false){
                inCoada[Vecin]=true;
                coada.push(Vecin);
            }
        }
    }
}
}

void afisare(){
for(int i=2;i<=n;i++){
    if(D[i]!=oo){
        out << D[i] << " ";
    }
    else {
        out << "0 ";
    }
}
}

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