#include <fstream>
#include <vector>

#define MARE 100000000
#define LIMITA 50001

using namespace std;

// n - numarul de noduri
// m - numarul de muchii
// s - sursa
// a - matricea costurilor
// d - distantele de la sursa la noduri
int i, n, m, l, c, s, d[LIMITA], x, y;
bool sel[1001];
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<unsigned short int> v[LIMITA], cost[LIMITA];

void dijkstra(int s) {
  int min, nmin, dn, nv;

  for (int i = 1; i <= n; i++)
    d[i] = MARE;
  sel[s] = true;  // Sursa este selectata.
  d[s] = 0;
  for (int pas = 2; pas <= n; pas++) {  // Alegem nodul neselectat, situat la distanta minima de sursa.
    min = MARE;
    for (i = 1; i <= n; i++)
      if (not sel[i])
        if (d[i] < min) {
          min = d[i];
          nmin = i;  // nmin devine roz
        }
    sel[nmin] = true;
    for (int iv = 0; iv < v[nmin].size(); iv++) { // doar vecinii lui nmin
      nv = v[nmin][iv]; // nodul vecin  
      if (not sel[nv]) {
        // dn = d[nmin] + a[nmin][i];
        dn = d[nmin] + cost[nmin][iv];
        if (dn < d[i])
            d[i] = dn;
      }
    }
  }
}

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;
}