#include<fstream>
#include<queue>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int n,m;
int d[50001];
vector < pair <int,int> > v[50001];
priority_queue < pair <int,int>, vector <pair <int,int> >, greater< pair <int,int> > > ord;
int INF = 1000000000;
void citire(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int ii,jj,g;
        cin>>ii>>jj>>g;
        v[ii].push_back({jj,g});
    }
}
void dijkstra(int start){
    for(int i=1;i<=n;i++)
        d[i]=INF;
    d[start]=0;
    ord.push({0,start});
    while(!ord.empty()){
        int elem = ord.top().second;
        int dist = ord.top().first;
        for(unsigned int i=0;i<v[elem].size();i++){
            int elemnou = v[elem][i].first;
            int distnou = v[elem][i].second;

            if(d[elemnou] > dist+distnou){
                d[elemnou] = dist+distnou;
                ord.push({d[elemnou],elemnou});
            }
        }
        ord.pop();
    }
}
int main(){
    citire();
    dijkstra(1);
    for(int i=2;i<=n;i++){
        if(d[i]==INF)
            cout<<"0 ";
        else
        cout<<d[i]<<" ";
    }
    return 0;
}