#include <bits/stdc++.h>
#define f first
#define s second
#define N 50001
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector< pair<int,int> >graf[N];//vectorul nostru
priority_queue< pair<int,int> >coada;//coada
int costuri[N];//costurile
int main() {
    int n,m,x,y,cost,i;
    fin>>n>>m;
    for(i=1; i<=m; ++i){
        fin>>x>>y>>cost;
        graf[x].push_back({y,cost});
    }

    coada.push({0,1});
    while(!coada.empty()){
        cost=-coada.top().f;//costul negativ
        i=coada.top().s;//vecinul
        coada.pop();
        if(costuri[i]>=0){//daca costul e mai mare ca 0
            costuri[i]=-cost-1; //alocal costul negativ
            for(auto it:graf[i])//parcurgem vecinii nodului
                if(!costuri[it.f] || cost+it.s<costuri[it.f]){//daca are un cost sau
                        //costul din nodul acesta e mai mic, le schimb
                    costuri[it.f]=cost+it.s;
                    coada.push({-costuri[it.f], it.f});//si introudcem in coada
                }
        }
    }

    for(i=2; i<=n; ++i)
        fout<< max(-costuri[i]-1,0)<<" ";

    return 0;
}