#include <fstream>

#define MARE 100000000

using namespace std;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

int a[1501][1501], sel[1501], d[1501], i, m, n, l, c, nc;

void dijkstra (int s) {
  int min,jmin,dn,j;

  for (i = 2 ; i <= n; i++)
    d[i] = a[s][i];   // Initializam distanta fata de sursa.
  sel[s] = 1; // Aratam ca sursa este selectata.
  d[s] = 0;   // Distanta de la sursa la sursa este 0.
  for (i = 2; i <= n; i++) {
    min = MARE;
    for (j = 2;j <= n;j++) // pentru fiecare nod
      if (sel[j] == 0)         // daca nu este selectat
        if (d[j] < min) {  // daca avem o valoare mai mica pentru distanta
          min = d[j];      // actualizam min
          jmin = j;        // retinem nodul care ne da minimul [jmin]
        }
    sel[jmin] = 1; // Includem nodul jmin in multimea nodurilor selectate.
    for (j = 2;j <= n;j++) // Pentru fiecare nod_
      if (sel[j] == 0) {           // neselectat
        dn = d[jmin] + a[jmin][j]; // Calculam distanta noua, folosind jmin.
        if (dn < d[j])        // Daca am gasit un lant mai scurt prin jmin,
          d[j] = dn;           // actualizam distanta de la sursa la nod.
      }
  }
}

int main () {
  fi >> n >> m;
  for (l = 1; l <= n; l++)
    for (c = 1; c <= n; c++)
      a[l][c] = MARE;
  for (i = 1; i <= m; i++) {
    fi >> l >> c; fi >> a[l][c];
  }
  dijkstra(1);
  for (i = 2; i <= n; i++) {
    if(d[i]==MARE)
    fo<<"0"<<' ';
    else
    fo << d[i] << ' ';
//		for (nc = i; p[nc]; nc = p[nc])
//			cout << nc << " - "; // prezentam lantul de la nodul curent la sursa
//		cout << s << endl;
  }
}