#include <cstdio>
#include <list>
#include <queue>
using namespace std;

#define NMAX 50001
#define COST_MAX 1<<29

int N, M, heap_size, distances[NMAX];
list<pair<int, int> > adj_list[NMAX];
int min_heap[NMAX], heap_poz[NMAX];

void readInput() {
	int i, from, to, cost;
	freopen("dijkstra.in","r",stdin);
	scanf("%d %d",&N,&M);
	for (i=0;i<M;i++) {
		scanf("%d %d %d",&from,&to,&cost);		
    adj_list[from].push_back(make_pair(to,cost));
	}	
  for (i=1;i<=N;i++) min_heap[i] = heap_poz[i] = i;
  heap_size = N;
}

void min_heapify(int i) {
  int smallest, left;
  do {
    smallest = i, left = i<<1;
    for (int k=left;k<=left+1;k++) {
      if (k<=heap_size && distances[min_heap[k]] < distances[min_heap[smallest]]) {
        smallest = k;
      } 
    }
    if (smallest == i) break;
    swap(min_heap[i],min_heap[smallest]);
    swap(heap_poz[min_heap[i]],heap_poz[min_heap[smallest]]);
    smallest = i;    
  }while(true);
}

void build_min_heap() {
  for (int i=heap_size/2;i>0;i--) {
    min_heapify(i);
  }
}

int extract_min() {
  int x = min_heap[1];
  swap(min_heap[1],min_heap[heap_size]);
  swap(heap_poz[min_heap[1]],heap_poz[min_heap[heap_size]]);
  heap_size--;
  min_heapify(1);
  return x;
}

void djikstra(int s) {
  for (int i=1;i<=N;i++) {
    distances[i] = COST_MAX;
  }
  distances[s] = 0;
  build_min_heap();
  while (heap_size > 0) {
    int u = extract_min();
    for (list<pair<int, int> >::iterator it = adj_list[u].begin();it!=adj_list[u].end();it++) {
      if (distances[it->first] > distances[u]+it->second) {
        distances[it->first] = distances[u]+it->second;
        min_heapify(heap_poz[it->first]);
      }
    }
  }
}

int main() {
  readInput();
  freopen("djikstra.out","w",stdout);
	djikstra(1);
  for (int i=2;i<=N;i++) {
    printf("%d ",(distances[i]==COST_MAX)?0:distances[i]);
	}
	printf("\n");
  return 0;
}