#include <queue>
#include <stdio.h>
#include <vector>

const int MAX_N = 50000;
const int INF = 1e9;

struct Node {
  int v;
  int cost;
  bool operator <(const Node& other) const {
    return this->cost > other.cost;
  }
};

std::vector<Node> G[1 + MAX_N];
int dist[1 + MAX_N];

int main() {

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

  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    dist[i] = INF;
  for (int i = 1; i <= m; i++) {
    int u, v, cost;
    scanf("%d%d%d", &u, &v, &cost);
    G[u].push_back(Node{v, cost});
  }
  std::priority_queue<Node> q;
  q.push(Node{1, 0});
  while (!q.empty()) {
    Node node = q.top();
    q.pop();
    if (dist[node.v] == INF) {
      dist[node.v] = node.cost;
      for (Node i : G[node.v])
        if (dist[i.v] == INF)
          q.push(Node{i.v, i.cost + dist[node.v]});
    }
  }
  for (int i = 2; i <= n; i++) {
    if (dist[i] == INF)
      printf("0 ");
    else
      printf("%d ", dist[i]);
  }
  printf("\n");

  fclose(stdin);
  fclose(stdout);

  return 0;
}