#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll NMAX=5e4+5;
set<pll> s;
ll dist[NMAX];
vector<pll> edg[NMAX];
int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    ll n,m;
    fin>>n>>m;
    for(ll i=0;i<m;i++){
        ll u,v,c;
        fin>>u>>v>>c;
        u--,v--;
        edg[u].push_back({v,c});
    }
    for(ll i=1;i<n;i++)
        dist[i]=1e12;
    s.insert({0,0});
    while(!s.empty()){
        ll u=s.begin()->second;
        for(auto it : edg[u]){
            if(dist[u]+it.second<dist[it.first]){
                s.erase({it.first,dist[it.first]});
                dist[it.first]=dist[u]+it.second;
                s.insert({it.first,dist[it.first]});
            }
        }
        s.erase(s.begin());
    }
    for(ll i=1;i<n;i++)
        if(dist[i]>=1e12) fout<<"0 ";
        else fout<<dist[i]<<' ';
    return 0;
}