//Dijkstra 40p  cu memorare graf cu matrice de adiacenta varianta O
//O(n*n)clasic nu se incadreaza in timp si in memorie
#include <fstream>
#define inf 100000000
using namespace std;
ifstream f("dijkstra.in"); ofstream g("dijkstra.out");
int a[1500][1500], sel[1500], d[1500], i, m, n, j, c, cost, s, x,y;
void dijkstra (int s) {//-------------------------------------------------------------
  int mini, dn, jmin, j;
  for (i = 1; 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 = 1; i <= n-2; i++) {
      mini = inf;
      for (j=1;j<=n;j++)            // pentru fiecare nod
          if (sel[j] == 0)          // daca nu este selectat
              if (d[j]< mini) {     // daca avem o valoare mai mica pentru distanta
                  mini = 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=1;j<=n;j++)
  if (sel[j]==0) {                  //  Pentru fiecare nod 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 () {
  f >> n >> m;
  for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
          a[i][j] = inf;
  for (i = 1; i <= m; i++) { f >> x >> y; f >> a[x][y]; }
  dijkstra(1);
  for (i = 2; i <= n; i++)
    if(d[i] == inf) g << "0 "<<' ';
    else  g << d[i] << ' ';
      g<<endl; return 0;
}