#include <bits/stdc++.h>
using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");

#define ll long long

const ll INF=LLONG_MAX;

ll n,m;
vector<vector<pair<ll,ll>>> g;


void disjkstra(){

    static vector<ll> dist(n+1,INF);
    dist[1]=0;
    struct cmp{
        bool operator() (ll a,ll b){
            return dist[a]>dist[b];
        };
    };
    priority_queue<ll, vector<ll>, cmp> pq;
    pq.push(1);
    vector<bool> viz(n+1,0);
    viz[1]=1;

    while(pq.size()){
        ll nd=pq.top();  pq.pop();
        viz[nd]=0;

        for(auto it:g[nd]){
            ll nnd=it.second, d=it.first+dist[nd];
            if(d<dist[nnd]){
                dist[nnd]=d;
                if(!viz[nnd])
                    pq.push(nnd), viz[nnd]=1;
            }
        }
    }
    for(ll i=2;i<dist.size();++i)
        fout<<(dist[i]==INF? 0:dist[i])<<" ";
}


int main() {
    fin>>n>>m;
    g.resize(n+1);
    for(ll i=1;i<=m;++i){
        ll a,b,c;
        fin>>a>>b>>c;
        g[a].push_back({c,b});
    }
    disjkstra();
}