#include<bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
queue<int> q;
vector<pair<int,int>> a[100001];
int v[1000001];
int main()
{
    memset(v, 0, sizeof(v));
  int n, m, i, h, d, k, y;
  fin>>n>>m;
  for(i=1; i<=m; i++){ fin>>d>>h>>y; a[d].push_back(make_pair(h, y));}
    q.push(1);
    for(i=1;i<=n;i++){
        sort(a[i].begin(),a[i].end());
    }
    while(!q.empty()){
        k=q.front();
        for(auto e:a[k]){
            if(v[e.first]==0&&v[e.first] >= v[k] + e.second){
                v[e.first]=v[k]+e.second;
                 q.push(e.first);
            }
        }
        q.pop();
    }
    for(y=2; y<=n; y++){
     fout<<v[y]<<' ';
   }
}