#include <fstream>
#include <set>
#include <vector>
#define int long long
using namespace std;
const int INF = 100000;
const int NMAX =50000; 

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector <pair<int, int> > adj[NMAX + 2];
int n, source;
void dijkstra(){
  vector <int> v;
  set<pair<int, int> > s;
  v.assign(NMAX + 1, INF);
  v[source] = 0;
  s.insert(make_pair(0, source));
  while(!s.empty()){
    int nod = s.begin()->second;
    s.erase(s.begin());
    for(auto vecin : adj[nod]){
      int to = vecin.first;
      int length = vecin.second;
      if(v[nod] + length < v[to]){
        s.erase(make_pair(v[to], to));
        v[to] = v[nod] + length;
        s.insert(make_pair(v[to], to));
      }
    }
  }
  for(int i = 2;i<=n;i++){
    if(v[i] == INF){
      out<<"0 ";
    }else{
      out<<v[i]<<" ";
    }
  }
}
signed main(){
  int from, to, cost, m;
  in>>n>>m;
  source =1;
  for(int i = 1;i<=m;i++){
    in>>from>>to>>cost;
    adj[from].push_back(make_pair(to, cost));
  }
  dijkstra();
  return 0;
}