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

#define MAX_M 250000
#define MAX_N 50000
#define NIL -1
#define INFTY 1000000000

typedef struct {
  int v, weight;
  int next;
} cell;

cell l[MAX_M];  // liste alocate static
int adj[MAX_N]; // capetele listelor
int dist[MAX_N];
std::queue <int> q;
bool inQueue[MAX_N];


void addEdge(int u, int v, int weight, int pos) {
  l[pos].v = v;
  l[pos].weight = weight;
  l[pos].next = adj[u];
  adj[u] = pos;
}

void bellmanFord(int u) {
  q.push(u);
  dist[u] = 0;
  do {
    int node = q.front();
    q.pop();
    inQueue[node] = 0;
    for (int i = adj[node]; i != NIL; i = l[i].next) {
      if (dist[node] + l[i].weight < dist[l[i].v]) {
        dist[l[i].v] = dist[node] + l[i].weight;
        if (!inQueue[l[i].v]) {
          q.push(l[i].v);
          inQueue[l[i].v] = 1;
        }
      }
    }
  } while (!q.empty());
}

int main(void) {
  FILE *f = fopen("dijkstra.in", "r");
  int n, m;

  fscanf(f, "%d%d", &n, &m);

  for (int i = 0; i < n; i++) {
    adj[i] = NIL;
    dist[i] = INFTY;
  }

  for (int i = 0; i < m; i++) {
    int u, v, weight;
    fscanf(f, "%d%d%d", &u, &v, &weight);
    addEdge(u - 1, v - 1, weight, i);
  }
  fclose(f);

  bellmanFord(0);

  f = fopen("dijkstra.out", "w");
  for (int i = 1; i < n; i++) {
    fprintf(f, "%d ", (dist[i] == INFTY) ? 0 : dist[i]);
  }
  fclose(f);
  return 0;
}