#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

#define MAX_N 50004

struct Edge {
  int node, cost;
};

vector<Edge> graph[MAX_N];

queue<int> bfsQueue;
int dist[MAX_N];

void addEdge(int a, int b, int cost) {
  graph[a].push_back({b, cost});
}

void bfs(int node) {
  int qFront;

  bfsQueue.push(node);
  dist[node] = 0;

  while (!bfsQueue.empty()) {
    qFront = bfsQueue.front();

    for (const Edge& edge : graph[qFront])
      if (!dist[edge.node] || dist[edge.node] > dist[qFront] + edge.cost) {
        bfsQueue.push(edge.node);
        dist[edge.node] = dist[qFront] + edge.cost;
      }

    bfsQueue.pop();
  }
}

int main() {
  FILE *fin, *fout;
  fin = fopen("bellmanford.in", "r");
  fout = fopen("bellmanford.out", "w");

  int n, m, i, a, b, cost;
  fscanf(fin, "%d%d", &n, &m);
  for (i = 0; i < m; ++i) {
    fscanf(fin, "%d%d%d", &a, &b, &cost);
    addEdge(a, b, cost);
  }

  bfs(1);

  for (i = 2; i <= n; ++i)
    fprintf(fout, "%d ", dist[i]);

  fclose(fin);
  fclose(fout);
  return 0;
}