#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX_NODES = 50001;
const int MAX_EDGES = 250001;
const int INFINITY = 999999999;

int N, M;
vector<pair<int, int>> graph[MAX_NODES];

void readData() {
  scanf("%d %d ", &N, &M);
  for (int i = 1; i <= M; i++) {
    int from, to, cost;
    scanf("%d %d %d ", &from, &to, &cost);

    graph[from].push_back({ to, cost });
  }
}

void shortestPath() {
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
  q.push({ 0, 1 });

  vector<int> distance(N + 1, INFINITY);
  vector<bool> isInQueue(N + 1, false);

  distance[1] = 0;
  isInQueue[1] = 1;

  while (!q.empty()) {
    int currentNode = q.top().second;

    q.pop();
    isInQueue[currentNode] = false;

    for (auto next: graph[currentNode]) {
      int nextNode = next.first, nextCost = next.second;

      if (distance[nextNode] > distance[currentNode] + nextCost) {
        distance[nextNode] = distance[currentNode] + nextCost;
        if (!isInQueue[nextNode]) {
          q.push({ distance[nextNode], nextNode });
          isInQueue[nextNode] = true;
        }
      }
    }
  }

  for_each(distance.begin() + 2, distance.end(), [](int value){ printf("%d ", value != INFINITY ? value : 0); });
}

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

  readData();
  shortestPath();

  return 0;
}