#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])? 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;
}
 
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()){
min = *Q.begin();
Q.erase(min);
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;
}