#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 dijkstra(int startNode, int nodes) {
  for (int i = 2; i <= nodes; i++) distMin[i] = PlusINF;

  distMin[startNode] = 0;
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

  pq.push({ 0, startNode });
  while (!pq.empty()) {
    int currDist = pq.top().first;
    int currNode = pq.top().second;

    pq.pop();

    if (currDist > distMin[currNode]) continue;

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

      if (distMin[nextNode] > distMin[currNode] + cost) {
        distMin[nextNode] = distMin[currNode] + cost;
        pq.push({ distMin[nextNode], nextNode });
      }
    }
  }
}


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(1, nodes);
  write_data();

  return 0;
}