#include <cstdio>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

#define INF 0x3f3f3f3f
#define MAXN 50010

int d[MAXN];

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

struct comp {
  bool operator()(const int &a, const int &b)const{
    return (d[a] > d[b])? 1: 0;
  }
};

int main(){

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

  int N, M, i, s, min;
  Node *graph[MAXN], *aux;
  bool use[MAXN];

  scanf("%d%d", &N, &M);

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

  for(i = 0; i < M; i++){
    aux = new Node;
    scanf("%d%d%d", &s, &aux->dest, &aux->cost);
    aux->next = graph[s];
    graph[s] = aux;
  }

  priority_queue<int, vector<int>, comp> Q;

  memset(d, INF, sizeof(d));
  memset(use, 0, sizeof(use));

  Q.push(1); d[1] = 0; use[1] = 1;

  while(!Q.empty()){
    min = Q.top();
    Q.pop();
    use[min] = 0;

    for(aux=graph[min]; aux; aux=aux->next){
      if(d[min]+aux->cost < d[aux->dest]){
	d[aux->dest] = d[min]+aux->cost;
	if(!use[aux->dest]){
	  Q.push(aux->dest);
	  use[aux->dest]=1;
	}
      }
    }
  }

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

  return 0;
}