#include<bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
queue<int> q;
vector<pair<int,int>> a[1001];
int v[50001];
int main()
{
  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);
    v[1]=0;
    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;
                 q.push(e.first);
            }
            else if(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]<<' ';
   }
}