#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);
  fill(distance.begin(), distance.end(), INFINITY);

  distance[1] = 0;

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

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

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

  //vector<int> newDistance;
  //newDistance.resize(distance.size() - 2);

  //transform(distance.begin() + 2, distance.end(), newDistance.begin(), [&](int value){ return value != INFINITY ? value : 0; });
  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;
}