#include <bits/stdc++.h>
#define f first
#define s second
#define N 50001
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector< pair<int,int> >a[N];
priority_queue< pair<int,int> >h;
int v[N];
int main() {
    int n,m,x,y,w,i;
    in>>n>>m;
    for(i=1; i<=m; ++i){
        in>>x>>y>>w;
        a[x].push_back({y,w});
    }
    h.push({0,1});
    while(!h.empty()){
        w=-h.top().f;
        i=h.top().s;
        h.pop();
        if(v[i]>=0){
            v[i]=-w-1;
            for(auto it:a[i])
                if(!v[it.f] || w+it.s<v[it.f]){
                    v[it.f]=w+it.s;
                    h.push({-v[it.f], it.f});
                }
        }
    }
    for(i=2; i<=n; ++i)
        out<<-v[i]-1<<" ";
    return 0;
}