#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
#define CHECKRET(x, y) if(!(x)) return (y);
#define SKIP(x) if((x)) continue;
typedef pair<int, int> pii;

#ifdef INFOARENA
#define ProblemName "dijkstra"
#else
#define ProblemName "fis"
#endif

#define InFile ProblemName ".in"
#define OuFile ProblemName ".out"

const int MAXN = 50010;

vector<pii> G[MAXN];
LL dst[MAXN];

void Djkstra() {
  priority_queue< pair<LL, int> > Q;
  memset(dst, 0x3F, sizeof dst);
  Q.push(mp(0LL, 0));
  dst[0] = 0;
  while (!Q.empty()) {
    int t = Q.top().second;
    LL dt = -Q.top().first;
    Q.pop();
    SKIP(dt != dst[t]);
    for (const auto &it : G[t]) {
      LL cand = dt + it.second;
      SKIP(cand >= dst[it.first]);
      dst[it.first] = cand;
      Q.push(mp(-cand, it.first));
    }
  }
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  int N, M;
  scanf("%d%d", &N, &M);
  while (M--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    --a, --b;
    G[a].push_back(mp(b, c));
  }
  Djkstra();
  for (int i = 1; i < N; ++i)
    printf("%lld ", (dst[i] == 0x3F3F3F3F) ? 0 : dst[i]);
  puts("");
  return 0;
}