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

#define NMAX 50001
#define COST_MAX 1<<29

int N, M, heap_size, distances[NMAX], min_heap[NMAX], heap_poz[NMAX];
list<pair<int, int> > adj_list[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));
	}
}

void move_up(int i) {
	int parent = i>>1;
	while (parent != 0 && distances[min_heap[parent]] > distances[min_heap[i]]) {
		swap(heap_poz[min_heap[i]],heap_poz[min_heap[parent]]);
		swap(min_heap[i],min_heap[parent]);
		i = parent;
		parent = i>>1;
	}
}

void move_down(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(heap_poz[min_heap[i]],heap_poz[min_heap[smallest]]);
    swap(min_heap[i],min_heap[smallest]);    
    smallest = i;    
  }while(true);
}

void insert_heap(int v) {
	min_heap[++heap_size] = v;
	heap_poz[v] = heap_size;
	move_up(heap_size);
}
int extract_min() {
  int x = min_heap[1];
  swap(heap_poz[min_heap[1]],heap_poz[min_heap[heap_size]]);
  swap(min_heap[1],min_heap[heap_size]);  
  heap_size--;
  move_down(1);
  return x;
}

void decreaseKey(int i, int val) {
	distances[min_heap[i]] = val;
	move_up(i);
}

void djikstra(int s) {
	int i;
    for (i=1;i<=N;i++) {
        distances[i] = COST_MAX;
    }
    distances[s] = 0;
  
    for (int i=1;i<=N;i++) {
	    insert_heap(i);
    }

    for (i=1;i<=N;i++) {
      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) {
		    decreaseKey(heap_poz[it->first], distances[u]+it->second);
        }
      }
	}  
}

int main() {
  readInput();
  freopen("dijkstra.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;
}