#include <cstdio>
#include <vector>
#include <utility>
#include <queue>

using namespace std;
vector < pair<int, int> > w[50002];
queue < int > q;
int N, M, x, y, l, d[50002], viz[50002];

void init_d(int d[], int N) {
  for (int i = 1; i <= N; ++i) {
    d[i] = 1<<30;
  }
}

inline void relax(int u, int v, int w) {
  if (d[v] > d[u] + w) {
    d[v] = d[u] + w;
  }
}

int main() {
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);

  scanf("%d %d", &N, &M);

  for (int i = 1; i <= M; ++i) {
    scanf("%d %d %d", &x, &y, &l);

    w[x].push_back( make_pair(y, l) );
  }

  init_d(d, N);
  d[1] = 0;

  for (int u = 1; u <= N; ++u) {
    q.push(u);
  }

  for (; !q.empty(); q.pop() ) {
    int u = q.front();
    viz[u] = true;

    for (int i = 0, l = w[u].size(); i < l; ++i) {
      relax(u, w[u][i].first, w[u][i].second);
    }
  }

  for (int u = 2; u <= N; ++u) {
    if (d[u] == 1<<30) d[u] = 0;
    printf("%d ", d[u]);
  }
  printf("\n");

  return 0;
}