#include<bits/stdc++.h>
using namespace std;
#define MAXN 50001

const int INF = 0x3f3f3f3f;

priority_queue <pair <int, int> > heap;
vector<pair<int, int> >g[MAXN];
int d[MAXN];
int n;
void dijkstra(int start){
  int i, cost, node, son, cost_son;
  for (i = 1; i <= n; i++)
    d[ i ] = INF;

  d[start]=0;
  heap.push({0, start});
  while(!heap.empty()){
    cost=-heap.top().first;
    node=heap.top().second;
    heap.pop();
    if(cost==d[node]){
      for(auto edge : g[node]){
        cost_son=edge.first;
        son=edge.second;
//        printf("%d %d\n", cost_son+cost, d[son]);
        if(cost_son+cost<d[son]){
          d[son]=cost_son+cost;
          heap.push({-d[son], son});
        }
      }
    }

  }
}
int main(){
  FILE*fin=fopen("dijkstra.in", "r");
  FILE*fout=fopen("dijkstra.out", "w");
  int m, i, a, b, c;
  fscanf(fin, "%d%d", &n, &m);
  for(i=1; i<=m; i++){
    fscanf(fin, "%d%d%d", &a, &b, &c);
    g[a].push_back({c, b});
  }
  dijkstra(1);
  for(i=2; i<=n; i++){
    if(d[i]==INF)
      fprintf(fout, "0 ");
    else
      fprintf(fout, "%d ", d[i]);
  }
  return 0;
}