#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
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];
  }
};
 
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;
}
 
set<int, comp> Q;
 
memset(d, INF, sizeof(d));
memset(use, 0, sizeof(use));
 
Q.insert(1); d[1] = 0; use[1] = 1;
 
  while(!Q.empty()){
    set<int, comp>::iterator it = Q.begin();
    min = *it;
    Q.erase(it);
    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.insert(aux->dest);
	  use[aux->dest]=1;
	}
      }
    }
  }
 
  for(i = 2; i <= N; i++)
    printf("%d ", (d[i]==INF)? 0: d[i]);
  printf("\n");
 
  return 0;
}