#include <fstream>
#include <iomanip>
#include <iostream>

#define MARE 100000000

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, a[1001][1001], d[1001];
bool sel[1001];
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

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

  for (int i = 1; i <= n; i++)
    d[i] = a[s][i];
  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 (i = 1; i <= n; i++)
            if (not sel[i]) {
                dn = d[nmin] + a[nmin][i];
                if (dn < d[i])
                    d[i] = dn;
            }
  }
}

int main() {
  fin >> n >> m;
  for (l = 1; l <= n; l++)
    for (c = 1; c <= n; c++)
        a[l][c] = MARE;
  for (i = 1; i <= m; i++) {
    fin >> l >> c;
    fin >> a[l][c];
  }
  dijkstra(1);
  for (i = 2; i <= n; i++)
    if (d[i] == MARE)
      fout << "0 ";
    else
      fout << d[i] << ' ';
  return 0;
}