#include <bits/stdc++.h>
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define MAXN 50005
#define PlusINF (1LL<<30)

using namespace std;

vector<int> V[MAXN];
vector<int> C[MAXN];

queue<int> Queue;
int distMin[MAXN];
bitset<MAXN> inQueue( 0 );

int nodes,
    edges;

void read_graph() {
  int x,
      y,
      cost;

  freopen(FIN, "r", stdin);
  scanf("%d %d", &nodes, &edges);

  for (int edge = 1; edge <= edges; ++edge) {
    scanf("%d %d %d", &x, &y, &cost);
    V[x].push_back(y);
    C[x].push_back(cost);
  }
}

void display_graph() {
  printf("Graful este reprezentat prin liste de adiacenta: \n");
  for (int i = 1; i <= nodes; i++) {
    printf("Node %d --->>", i);
    for (int j = 0; j < V[i].size(); ++j) {
      cout << V[i][j] << " ";
    }
  }
}

void display_costs() {
  printf("Graful costurilor: ");
  for (int i = 1; i <= nodes; i++) {
    printf("Node %d --->>", i);
    for (int j = 0; j < C[i].size(); ++j) {
      cout << C[i][j] << " ";
    }
  }
}

void dijkstra() {
  for (int i = 2; i <= nodes; i++) distMin[i] = PlusINF;

  // distanta de la nodul 1 la nodul 1 este 0
  distMin[1] = 0;

  Queue.push(1);

  // marchez faptul ca nodul 1 se afla in coada
  inQueue[1] = true;

  // atat timp cat avem noduri in coada, sa executam instructiunile
  while (!Queue.empty()) {
    int curr = Queue.front();
    Queue.pop();

    // nodul curr nu se mai afla in coada
    inQueue[curr] = false;

    for (int i = 0; i < V[curr].size(); i++) {
      int y = V[curr][i];
      int cost = C[curr][i];

      if (distMin[y] > distMin[curr] + cost) {
        distMin[y] = distMin[curr] + cost;
        if (!inQueue[y]) {
          Queue.push(y);
          inQueue[y] = true;
        }
      }

    }
  }
}

void write_data() {
  // distMin
  freopen(FOUT, "w", stdout);

  for (int i = 2; i <= nodes; i++) printf("%d ", (distMin[i] < PlusINF) ? distMin[i] : 0);
}

int main() {

  read_graph();
  // display_graph();
  // display_costs();

  dijkstra();
  write_data();

  return 0;
}