#include <cstdio>

const int MAX_N = 50000;
const int MAX_M = 250000;
const int INF = 1000000000;
int mc[1+MAX_M], cost[1+MAX_M], next[1+MAX_M];
int last[1+MAX_N], dist[1+MAX_N], poz[1+MAX_N];

int top;
int heap[MAX_N];

bool cmp(int a, int b) {
  return dist[a] < dist[b];
}

int root() {
  return heap[0];
}

inline void swap(int *a, int *b) {
  int aux;
  aux = *a;
  *a = *b;
  *b = aux;
}

void up(int p) {
  while(p > 0 && cmp(heap[p], heap[p / 2])) {
    swap(&heap[p], &heap[p / 2]);
    swap(&poz[heap[p]], &poz[heap[p / 2]]);
    p = p / 2;
  }
}

void down(int p) {
  int targ;
  while(p < top) {
    targ = p;
    if(p * 2 + 1 < top && cmp(heap[2 * p + 1], heap[targ]))
      targ = p * 2 + 1;
    if(p * 2 + 2 < top && cmp(heap[2 * p + 2], heap[targ]))
      targ = p * 2 + 2;
    if(targ == p)
      p = top;
    else {
      p = targ;
      swap(&heap[p], &heap[targ]);
      swap(&poz[heap[p]], &poz[heap[targ]]);
    }
  }
}

void add(int a) {
  poz[a] = top;
  heap[top] = a;
  up(top);
  top++;
}

void erase(int pos) {
  top--;
  swap(&heap[pos], &heap[top]);
  swap(&poz[heap[pos]], &poz[heap[top]]);
  down(pos);
}

int main() {
  int n, m, a, b, c, x;
  FILE *fin = fopen("dijkstra.in", "r");
  fscanf(fin, "%d%d", &n, &m);
  for(int i = 1; i <= m; ++i) {
    fscanf(fin, "%d%d%d", &a, &b, &c);
    next[i] = last[a];
    mc[i] = b;
    last[a] = i;
    cost[i] = c;
  }
  fclose(fin);

  dist[0] = INF;
  add(1);
  for(int i = 2; i <= n; ++i) {
    dist[i] = INF;
    add(i);
  }

  while(top > 0) {
    x = root();
    erase(0);
    int i = last[x];
    while(i != 0) {
      if(dist[x] + cost[i] < dist[mc[i]]) {
        dist[mc[i]] = dist[x] + cost[i];
        up(poz[mc[i]]);
      }
      i = next[i];
    }
  }

  FILE *fout = fopen("dijkstra.out", "w");
  for(int i = 2; i <= n; ++i)
    if(dist[i] == INF)
      fprintf(fout, "0 ");
    else
      fprintf(fout, "%d ", dist[i]);
  fclose(fout);
  return 0;
}