#include <fstream>
#include <vector>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int inf=1e9;
struct nr{
    int b,c;
};
vector<vector<nr>>gr;
vector<int>distanta;
const int MAXVAL=50000;
pair<int,int> v[MAXVAL+1];
int n=0;
int parinte(int n){
    return n/2;
}
int copil_stang(int n){
    return 2*n;
}
int copil_drept(int n){
    return 2*n+1;
}
void Heap_in_sus(int k){
    while(k>1 && v[parinte(k)].first>v[k].first){
        swap(v[k],v[parinte(k)]);
        k=parinte(k);
    }
}
void Heap_in_jos(int n,int k){
    int copil;
    while(true){
        copil=0;
        if(copil_stang(k)<=n){
            copil=copil_stang(k);
            if(copil_drept(k)<=n && v[copil].first>v[copil_drept(k)].first){
                copil=copil_drept(k);
            }
        }
        if(copil && v[copil].first>v[k].first){
            swap(v[k],v[copil]);
            k=copil;
        }else{
            break;
        }

    }
    }
void insereaza(int& n,const int& dist,const int& nod){
    n++;
    v[n].first=dist;
    v[n].second=nod;
    Heap_in_sus(n);
}
void extrage_minim(int&n){
    swap(v[1],v[n]);
    n--;
    Heap_in_jos(n,1);

}
void dijkstra(const int& nod){
    distanta[nod]=0;
    insereaza(n,distanta[nod],nod);
    while(n>0){
        int nod_curent=v[1].second;
        int val_curent=v[1].first;
        extrage_minim(n);
        if(val_curent!=distanta[nod_curent]){
            continue;
        }
        for(const auto&x:gr[nod_curent]){
            if(distanta[x.b]>distanta[nod_curent]+x.c){
                distanta[x.b]=distanta[nod_curent]+x.c;
                insereaza(n,distanta[x.b],x.b);
            }
        }
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    int nod_1,nod_2,cost;
    gr.resize(n+1);
    distanta.resize(n+1,inf);
    for(int i=1;i<=m;i++){
        cin>>nod_1>>nod_2>>cost;
        gr[nod_1].push_back({nod_2,cost});
    }
    dijkstra(1);
    for(int i=2;i<=n;i++){
        if(distanta[i]==inf){
            cout<<0<<" ";
        }else{
            cout<<distanta[i]<<" ";
        }
    }
}