#pragma GCC optimize ("O3")
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

#define NMAX 100001

int n,m,d[NMAX];
vector<pair<int,int>>g[NMAX];
priority_queue<pair<int,int>>pq;
signed main(){
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif // LOCAL
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z});
        // g[y].push_back({x,z});
    }
    fill(d+2,d+n+1,0x7fffffff);
    d[1]=0;
    pq.push({0,1});
    while(!pq.empty()){
        int i=pq.top().second,c=pq.top().first;
        pq.pop();
        if(c>d[i])continue;
        for(const auto&it:g[i]){
            if(d[it.first]>d[i]+it.second){
                d[it.first]=d[i]+it.second;
                pq.push({d[it.first],it.first});
            }
        }
    }
    for(int i=2;i<=n;++i)cout<<(0x7fffffff!=d[i]?d[i]:0)<<" ";
    return 0;
}