#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

#define MARE 100000000
#define LIMITA 50001

using namespace std;

struct NOD {
  unsigned short int n;
  int d;
};

int i, n, m, x, y, c, s, d[LIMITA];
int p[LIMITA];
vector<unsigned short int> v[LIMITA], cost[LIMITA];

bool sel[LIMITA];
//ifstream fin("dijkstra.in");
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector <pair<int, int>> h; // -distanta, nod


void showh() {
  if (not h.empty())
    for (int i = 0; i < h.size(); i++)
      cout << '(' << -h[i].first << ", " << h[i].second << ") ";
  cout << endl;
}


void dijkstra (int s) {
  int nmin, dn, i, iv, nv;
  NOD nod;

  for (i = 2; i <= n; i++)
    d[i] = MARE; // Initializam distanta fata de sursa.
  d[s] = 0;
  h.push_back(make_pair(0, 1)); // Punem sursa in coada.
  //showh();
  while (not h.empty()) {
    nmin = h[0].second;  // Nodul cu distanta minima de la sursa.
    //cout << "nmin = " << nmin << endl;
    pop_heap(h.begin(), h.end()); h.pop_back();
    //showh();
    //sel[nmin] = true; // retinem nodul care ne da minimul [nmin]
    for (iv = 0; iv < v[nmin].size(); iv++) { // doar vecinii lui nmin
      nv = v[nmin][iv]; // nodul vecin
      //cout << "nv = " <<  nv << endl;
      //if (not sel[nv]) {
        dn = d[nmin] + cost[nmin][iv]; // calculam distanta noua, folosind nmin.
        if (d[nv] > dn) { // Daca am gasit un lant mai scurt prin nmin,
          d[nv] = dn;     // actualizam distanta de la sursa la nv.
          h.push_back(make_pair(-d[nv], nv));
          //showh();
        }
      //}
    }
  }
}

int main () {
  fin >> n >> m;
  for (i = 1; i <= m; i++) {
    fin >> x >> y;
    v[x].push_back(y); // vectori de vecini
    fin >> c;
    cost[x].push_back(c);
  }
  dijkstra(1);
  for (i = 2; i <= n; i++) {
    if (d[i] == MARE)
      fout << "0 ";
    else
      fout << d[i] << ' ';
  }
  return 0;
}