#include <iostream>
#include <bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int nmax=5e4+1;
int n,m,x,y,vl;
vector<vector<pair<int,int> > > g;
vector<int> d;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;




int main()
{
    fin>>n>>m;
    d.assign(n+1,-1);
    g.assign(n+1,vector<pair<int,int> >());
    for(int i=0;i<m;i++){
        fin>>x>>y>>vl;
        g[x].push_back({y,vl});
    }
    d[1]=0;
    q.push({0,1});
    while(!q.empty()){
        x=q.top().second;
        q.pop();

            for(pair<int,int> i:g[x]){
                if(d[i.first]>(d[x]+i.second)||d[i.first]==-1){
                d[i.first]=d[x]+i.second;
                q.push({d[i.first],i.first});
                }
            }

    }
    for(int i=2;i<=n;i++){
        if(d[i]!=-1)
        fout<<d[i]<<" ";
        else fout<<0<<" ";
    }
}