/*
  Copyright 2011 Marek "p2004a" Rusinowski
  Dijkstra algorithm
*/
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
 
#define MAXN 1000000
#define INF 0x7FFFFFF0
 
std::vector<std::pair<int, int> > edges[MAXN];
int d[MAXN], n, m;
 
struct cmp {
  bool operator() (int a, int b) {
    if (d[a] < d[b]) return true;
    if (d[a] > d[b]) return false;
    return a < b;
  }
};
 
void dijkstra(int v) {
  std::set<int, cmp> q;
  std::fill(d, d + n, INF);
  q.insert(v);
  d[v] = 0;
  while (!q.empty()) {
    int v = *(q.begin());
    q.erase(q.begin());
    for (unsigned i = 0; i < edges[v].size(); ++i) {
      if (d[v] + edges[v][i].second < d[edges[v][i].first]) {
        q.erase(edges[v][i].first);
        d[edges[v][i].first] = d[v] + edges[v][i].second;
        q.insert(edges[v][i].first);
      }
    }
  }
}
 
int main() {
  int a, b, c;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d %d %d", &a, &b, &c);
    edges[--a].push_back(std::make_pair(--b, c));
    edges[b].push_back(std::make_pair(a, c));
  }
  dijkstra(0);
  for (int i = 0; i < n; ++i) {
    printf("%d ", d[i]);
  }
  printf("\n");
  return 0;
}
 

LyoKICBDb3B5cmlnaHQgMjAxMSBNYXJlayAicDIwMDRhIiBSdXNpbm93c2tpCiAgRGlqa3N0cmEgYWxnb3JpdGhtCiovCiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxzZXQ+CgojZGVmaW5lIE1BWE4gMTAwMDAwMAojZGVmaW5lIElORiAweDdGRkZGRkYwCgpzdGQ6OnZlY3RvcjxzdGQ6OnBhaXI8aW50LCBpbnQ+ID4gZWRnZXNbTUFYTl07CmludCBkW01BWE5dLCBuLCBtOwoKc3RydWN0IGNtcCB7CiAgYm9vbCBvcGVyYXRvcigpIChpbnQgYSwgaW50IGIpIHsKICAgIGlmIChkW2FdIDwgZFtiXSkgcmV0dXJuIHRydWU7CiAgICBpZiAoZFthXSA+IGRbYl0pIHJldHVybiBmYWxzZTsKICAgIHJldHVybiBhIDwgYjsKICB9Cn07Cgp2b2lkIGRpamtzdHJhKGludCB2KSB7CiAgc3RkOjpzZXQ8aW50LCBjbXA+IHE7CiAgc3RkOjpmaWxsKGQsIGQgKyBuLCBJTkYpOwogIHEuaW5zZXJ0KHYpOwogIGRbdl0gPSAwOwogIHdoaWxlICghcS5lbXB0eSgpKSB7CiAgICBpbnQgdiA9ICoocS5iZWdpbigpKTsKICAgIHEuZXJhc2UocS5iZWdpbigpKTsKICAgIGZvciAodW5zaWduZWQgaSA9IDA7IGkgPCBlZGdlc1t2XS5zaXplKCk7ICsraSkgewogICAgICBpZiAoZFt2XSArIGVkZ2VzW3ZdW2ldLnNlY29uZCA8IGRbZWRnZXNbdl1baV0uZmlyc3RdKSB7CiAgICAgICAgcS5lcmFzZShlZGdlc1t2XVtpXS5maXJzdCk7CiAgICAgICAgZFtlZGdlc1t2XVtpXS5maXJzdF0gPSBkW3ZdICsgZWRnZXNbdl1baV0uc2Vjb25kOwogICAgICAgIHEuaW5zZXJ0KGVkZ2VzW3ZdW2ldLmZpcnN0KTsKICAgICAgfQogICAgfQogIH0KfQoKaW50IG1haW4oKSB7CiAgaW50IGEsIGIsIGM7CiAgc2NhbmYoIiVkICVkIiwgJm4sICZtKTsKICBmb3IgKGludCBpID0gMDsgaSA8IG07ICsraSkgewogICAgc2NhbmYoIiVkICVkICVkIiwgJmEsICZiLCAmYyk7CiAgICBlZGdlc1stLWFdLnB1c2hfYmFjayhzdGQ6Om1ha2VfcGFpcigtLWIsIGMpKTsKICAgIGVkZ2VzW2JdLnB1c2hfYmFjayhzdGQ6Om1ha2VfcGFpcihhLCBjKSk7CiAgfQogIGRpamtzdHJhKDApOwogIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICBwcmludGYoIiVkICIsIGRbaV0pOwogIH0KICBwcmludGYoIlxuIik7CiAgcmV0dXJuIDA7Cn0K

MyAyCjEgMiAxCjIgMyAx

3 2
1 2 1
2 3 1