#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;
  while (true) {
    int nod = -1, d = 1e9;
    for (int i = 1; i <= n; i++) {
      if (!marcat[i] && dist[i] < d) {
        d = dist[i];
        nod = i;
      }
    }
    if (nod == -1) break;
    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] = dist[nod] + cost;
      }
    }
    marcat[nod] = true;
  }
  for (int i = 2; i <= n; i++){
    cout << dist[i] << " ";
  }
  return 0;
}