#include <cstdio>
#include <cstdlib>
#define MAXN 50010
#define MAXM 250010
#define INF 2147483647

struct Edge {
  int sta, end, cost;
};

// comparison function for qsort
int comparator(const void *a, const void *b){
  return (((Edge*)a)->sta-((Edge*)b)->sta);
}

int main(){

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

  Edge graph[MAXM];
  int ncost[MAXN], pos[MAXN], i, j, N, M, cur, curpos, cost, lowest, next;
  bool visited[MAXN];

  scanf("%d%d", &N, &M);
  for(i = 0; i < M; i++){
    scanf("%d%d%d", &(graph[i].sta), &(graph[i].end), &(graph[i].cost));
  }

  // sort edges by start position
  qsort(graph, M, sizeof(Edge), comparator);

  // record each starting point of a new node
  cur = 0;
  for(i = 0; i < M; i++){
    if(cur != graph[i].sta)
      pos[++cur] = i;
  }
    
  // set initial values
  for(i = 1; i <= N; i++){
    visited[i] = false;
    ncost[i]   = INF;
  }
    
  // algorithm
  ncost[1] = 0; cur = 1; curpos = 0;
  while(true){

    lowest = INF; next = -1;
    while(graph[curpos].sta == cur){
      if(!visited[graph[curpos].end]){
	// check cost
	cost = ncost[cur] + graph[curpos].cost;
	if(cost < ncost[graph[curpos].end])
	  ncost[graph[curpos].end] = cost;
	// check if this is the next node
	if(ncost[graph[curpos].end] < lowest)
	  next = graph[curpos].end;
      }
      curpos++;
    }
    
    visited[cur] = true;
    if(next == -1){
      for(i = 1; i <= N; i++){
	if(!visited[i]){
	  next = i;
	  break;
	}
      }
      if(i > N)
	break;
    }
    cur = next; curpos = pos[cur];
    
  }
  
  for(i = 2; i <= N; i++)
    printf("%d ", ncost[i]);
  printf("\n");

  return 0;

}