#include <bits/stdc++.h>
using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
const int maxn = 5e4 + 1;
vector <pair <int, int> > ad [maxn];
// ad[i] -> vector <int> -> toate j-urile in care poti ajunge din i
int dist[maxn]; // dist[i] -> distanta de la nodul 1 la nodul i
bool marcat[maxn]; // marcat[i] -> daca am procesat nodul i

int main() {
  int n,m;
  in >> n >> m;
  for (int i = 0; i <= n; i++){
    dist[i] = 1e9;
  }
  for (int i = 0; i < m; i++){
    int x,y,c;
    in >> x >> y >> c;
    ad[x].push_back({y, c});
  }

  // for (int i = 1; i <= n; i++){
  //   for (int j = 0; j < ad[i].size(); j++){
  //     cout << i << " -> " << ad[i][j].first << ": cost " << ad[i][j].second << "\n";
  //   }
  // }
  dist[1] = 0;
  set <pair <int, int> > s; // (x, y) => x distanta minima sa ajungi din 1 pana la nodul y
  s.insert({0, 1}); // x = dist[y]
  while (!s.empty()) {
    pair <int, int> pereche = *s.begin();
    int nod = pereche.second;
    s.erase(s.begin());
    for (int i = 0; i < ad[nod].size(); i++){
      int urmator = ad[nod][i].first, cost = ad[nod][i].second;
      if (dist[nod] + cost < dist[urmator]) {
        // (dist[urmator]; urmator)
        s.erase({dist[urmator], urmator});
        dist[urmator] = dist[nod] + cost;
        s.insert({dist[urmator], urmator});
      }
    }
  }
  for (int i = 2; i <= n; i++){
    out << (dist[i] ? dist[i] : 0) << " ";
  }
  return 0;
}