#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 50000
#define MAXM 250000
#define MAXVAL 2000000000

using namespace std;

vector<vector<int>> v;
vector<vector<int>> cost;
int hp[MAXM], dp[MAXM], hpi, f[MAXN];

static inline int parent(int x){
  if(x == 0)
    return 0;
  return (x-1)/2;
}
static inline int lchild(int x){
  return x*2 + 1;
}
static inline int rchild(int x){
  return x*2 + 2;
}

void swapx(int a, int b){
  int aux = hp[a];
  hp[a] = hp[b];
  hp[b] = aux;

  aux = dp[a];
  dp[a] = dp[b];
  dp[b] = aux;
}

void upHeap(int x){
  // printf("dp[%d] = %d  <  dp[%d] = %d ?\n", x, dp[x], parent(x), dp[parent(x)]);
  while(dp[x] < dp[parent(x)]){
    swapx(x, parent(x));
    x = parent(x);
  }
}

void downHeap(int x){
  int minp;

  while(dp[x] > dp[lchild(x)] || dp[x] > dp[rchild(x)]){
    if(dp[lchild(x)] < dp[rchild(x)])
      minp = lchild(x);
    else
      minp = rchild(x);

    swapx(x, minp);
    x = minp;
  }
}

void addHeap(int x, int dist){
  // printf("Add %d - %d at position %d\n", x, dist, hpi);
  hp[hpi] = x;
  dp[hpi] = dist;
  hpi ++;
  upHeap(hpi - 1);
}
void removeHeap(){
  // printf("Remove\n");
  swapx(0, hpi-1);
  hpi --;
  dp[hpi] = MAXVAL;
  downHeap(0);
}

int main(){
  int n, m, a, b, c, i, id, dist;

  ifstream fin ("dijkstra.in");
  fin >> n >> m;
  v.resize(n);
  cost.resize(n);

  for(i = 0; i < m; i ++){
    fin >> a >> b >> c;
    a --;
    b --;
    v[a].push_back(b);
    cost[a].push_back(c);
  }
  fin.close();

  for(i = 0; i < MAXM; i ++){
    dp[i] = MAXVAL;
  }
  for(i = 0; i < MAXN; i ++){
    f[i] = -1; 
  }

  addHeap(0, 0);
  while(hpi > 0){
    // for(int ii = 0; ii < hpi; ii ++)
    //   printf("%d - %d   ", hp[ii], dp[ii]);
    // // printf("\n");
    // printf("\n");

    id = hp[0];
    dist = dp[0];
    removeHeap();

    if(f[id] == -1){
      f[id] = dist;
      for(i = 0; i < v[id].size(); i ++){
        if(f[v[id][i]] == -1){
          addHeap(v[id][i], dist + cost[id][i]);
        }
      }
    }
  }

  ofstream fout ("dijkstra.out");
  for(i = 1; i < n; i ++){
    if(f[i] == -1)
      fout << "0 ";
    else
      fout << f[i] << ' ';
  }
  fout << endl;
  fout.close();

  return 0;
}