#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
vector <pair<int,int>> a[50001];
int dist[50001];
priority_queue <pair <int, int>>pq;

int main()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int n, m, x, y, z, d, poz, i, dist_cur;
    fin>>n>>m;
    for(i=0;i<m;i++){
        fin>>x>>y>>z;
        x--;
        y--;
        a[x].push_back({y,z});
    }
    for(i=1;i<=n;i++){
        dist[i]=-1;
    }
    pq.push({0,0});
    while(!pq.empty()){
        auto [dist_cur, poz]=pq.top();
        pq.pop();
       // cout<<poz<<' '<<dist_cur<<' ';
        if(dist_cur!=dist[poz]){
         //   cout<<'\n';
            continue;
        }
        //cout<<a[poz].size()<<'\n';
        for(i=0;i<a[poz].size();i++){
           // cout<<a[poz][i].first<<' '<<dist[a[poz][i].first]<<' '<<dist[poz]+a[i][poz].second<<'\n';
            if(dist[a[poz][i].first]==-1||dist[a[poz][i].first]>dist[poz]+a[i][poz].second){
                dist[a[poz][i].first]=dist[poz]+a[poz][i].second;
                pq.push({dist[a[poz][i].first],a[poz][i].first});
            }
        }
      //  cout<<'\n'<<'\n';
    }
    for(i=1;i<n;i++){
        fout<<dist[i]<<' ';
    }
    return 0;
}