#include <iostream>
#include <string.h>
#include <string>
#include <bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
typedef long long ll;
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define XD return cout<<ans[1],void();
#define DX return cout<<ans[0],void();
#define spit(x) return cout<<x<<'\n',void()
typedef pair<ll,ll> pll;
typedef array<ll,2> ll2;
typedef array<ll,4> ll4;
string ans[]={"NO\n","YES\n"};
const ll CMAX=20001;
void solve(){
    ll n,i,j,k,l,m,a,b,c;
    cin>>n>>m;
    deque<queue<ll>>bucks(CMAX);
    vector<vector<ll2>>vec(n+1);
    vector<ll>cst(n+1,1e15);
    for(i=1;i<=m;i++){
        cin>>a>>b>>c;
        vec[a].push_back({c,b});
    }
    queue<ll>empt;
    ll delt=0,cnt=1;
    bucks[0].push(1);
    cst[1]=0;
    ll nod;
    while(cnt>0){
        while(bucks[0].empty()){
            bucks.pop_front();
            bucks.push_back(empt);
            delt++;
        }
        nod=bucks[0].front();
        bucks[0].pop();
        cnt--;
        if(cst[nod]!=delt)continue;
        for(auto [c,y]:vec[nod]){
            if(delt+c < cst[y]){
                cnt++;
                bucks[c].push(y);
                cst[y]=delt+c;
            }
        }
    }
    for(i=2;i<=n;i++)cout<<(cst[i] == 1e15 ? 0ll : cst[i])<<' ';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("dijkstra.in","r",stdin);
    //freopen("dijkstra.out","w",stdout);
    //ll t;cin>>t;while(t--)
    solve();
    return 0;
}