#include <bits/stdc++.h>

using namespace std;
ifstream fin ("dij.in");
ofstream fout ("dij.out");

int n,m,i,x,y,d,apropiat,nod,dist,distanta[1000001],vizitat[1000001];
vector<pair<int,int>> v[1000001];
priority_queue<pair<int,int>> q;
int main()
{
    fin>>n>>m;
    while(fin>>x>>y>>d){
        v[x].push_back({y,d});
    }
    for(int i=1;i<=n;++i){
        distanta[i]=1000001;
    }
    distanta[1]=0;
    q.push({0,1});
    while(!q.empty()){
        apropiat=q.top().second;
        q.pop();
        if(vizitat[apropiat]==0){
            vizitat[apropiat]=1;
            for(auto element: v[apropiat]){
                nod=element.first;
                dist=element.second;
                if(distanta[nod]>distanta[apropiat]+dist){
                    distanta[nod]=distanta[apropiat]+dist;
                    q.push({-distanta[nod],nod});
                }
            }
        }
    }
    for(i=2;i<=n;i++){
        if(distanta[i]==1000001)fout<<-1<<" ";
        else fout<<distanta[i]<<" ";
    }
    return 0;
}