#include<bits/stdc++.h>
using namespace std;
const int N=50002, oo=1<<30;
unsigned int viz[N],t[N],n,m,n1;
long long d[N];
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

vector <pair<int,int>>L[N];
priority_queue<pair<int,int>>q;

void citire(){
unsigned int i,x,y,c;

in>>n>>m;
for(i=1;i<=m;++i){
    in>>x>>y>>c;
    L[x].push_back({y,c});
}
}

void dij(){
unsigned int i,j,nc,nv,cv;
for(i=1;i<=n;++i)d[i]=oo;
d[1]=0;
t[1]=0;
q.push({d[1],1});

while(!q.empty()){
    nc=q.top().second;
    q.pop();
    if(!viz[nc]){
        viz[nc]=1;
        for(j=0;j<L[nc].size();++j)
        {
            nv=L[nc][j].first;
            cv=L[nc][j].second;
            if(d[nv]>d[nc]+cv){
                d[nv]=d[nc]+cv;
                t[nv]=nc;
                q.push({-d[nv],nv});
            }
        }

    }
}

}

void drum(int x){
if(t[x])drum(t[x]);
cout<<x<<" ";
}

void afis(){
int i;

for(i=2;i<=n;++i){
    if(d[i]<oo)out<<d[i]<<" ";
    else out<<0<<" ";

}}
int main(){
citire();
dij();
afis();

in.close();
out.close();
return 0;}