#include <cstdio>
#include <string.h>
#define MAXN 50010
#define INF  1073741824

struct node {
  int dest, cost;
  node *next;
};

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

inline void read(node *graph[], int *N, int *M){
  
  int a, b, c;
  node *aux;

  scanf("%d%d", N, M);
  for(int i = 0; i < *M; i++){
    scanf("%d%d%d", &a, &b, &c);
    aux = new node;
    aux->dest = b;
    aux->cost = c;
    aux->next = graph[a];
    graph[a] = aux;
  }

}

// update heap element at the given position
inline void upheap(int *heap, int child, int *dist, int *pos){

  int parent;
  while(child > 1){
    parent = child>>1;
    if(dist[heap[child]] < dist[heap[parent]]){
      pos[heap[child]] = parent;
      pos[heap[parent]] = child;

      swap(heap, child, parent);
      child = parent;
    }
    else
      return;
  }
}

// delete heap root 
inline void downheap(int *heap, int *size, int *dist, int *pos){

  swap(heap, 1, (*size)--);

  int j = 1, i;
  while(true){
    i = j;
    if((i<<1)+1 <= *size){
      if(dist[heap[i]] > dist[heap[i<<1]])
	j = i<<1;
      if(dist[heap[j]] > dist[heap[(i<<1)+1]])
	j = (i<<1)+1;
    } else if(i<<1 <= *size){
      if(dist[heap[i]] > dist[heap[i<<1]])
	j = i<<1;
    }

    if(i != j){
      pos[heap[i]] = j;
      pos[heap[j]] = i;

      swap(heap, i, j);
    }
    else
      break;
  }
}

int main(){

  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);

  node *graph[MAXN], *aux;
  // heap contains the nodes and pos contains the index's(=node's tag) position in the heap
  int dist[MAXN], heap[MAXN], pos[MAXN];
  int N, M, size, min, i;

  memset(graph, NULL, sizeof(graph));

  read(graph, &N, &M);
      
  for(i = 1; i <= N; i++){
    dist[i] = INF; pos[i] = -1;
  }

  dist[1] = 0; size = 1; heap[size] = 1; pos[1] = size;

  // while heap isn't emty
  while(size){

    // extract node with smallest distance to source
    aux = graph[(min=heap[1])];
    pos[heap[size]] = 1; 
    downheap(heap, &size, dist, pos);

    while(aux != NULL){
      if(dist[aux->dest] > dist[min]+aux->cost){
	dist[aux->dest] = dist[min]+aux->cost;

	// if node was visited update it else add new element to heap
	if(pos[aux->dest] != -1)
	  upheap(heap, pos[aux->dest], dist, pos);
	else {
	  heap[++size] = aux->dest;
	  pos[heap[size]] = size;
	  upheap(heap, size, dist, pos);
	}
      }
      aux = aux->next;
    }  
    
  }

  for(i = 2; i <= N; i++)
    printf("%d ", dist[i]==INF?0:dist[i]);
  printf("\n");

  return 0;

}