#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
#define MARE 100000000
#define LIMITA 50001

using namespace std;

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

struct cmp {
  bool operator()(const NOD& a, const NOD& b) const {
    return (a.d > b.d); // descrescator
  }
};

int i, n, m, l, c, s, d[LIMITA];
bool sel[LIMITA];
vector <unsigned short int> v[LIMITA], cost[LIMITA];
priority_queue<NOD, vector<NOD>, cmp> pq, printq;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void dijkstra (int s) {
  int nmin, dn, i, j, nc, nj;
  NOD nod;
  for (i = 2; i <= n; i++)
    d[i] = MARE; // Initializam distanta fata de sursa.
  sel[s] = true; d[s] = 0;
  nod.n = 1; nod.d = 0;
  pq.push(nod);
  while (not pq.empty())
  {
      nod = pq.top(); pq.pop();
      nmin = nod.n;
      sel[nmin] = true;
      for(int i=0;i<v[nmin].size();i++)
      {
          int nv;
          nv = v[nmin][i];
          if(!sel[nv])
          {
              dn=d[nmin]+cost[nmin][i];
              if(d[nv]>dn) {
                d[nv]=dn;
                nod.n = nv;
                nod.d = d[nv];
                pq.push(nod);
              }
          }

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

int main () {
  fin >> n >> m;
  for (i = 1; i <= m; i++) {
    int x,y;
    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;
}