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

using namespace std;

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

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

void upHeap(int x){
  while(dp[x] < dp[parent(x)]){
    swap(hp[x], hp[parent(x)]);
    swap(dp[x], dp[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);

    swap(hp[x], hp[minp]);
    swap(dp[x], dp[minp]);
    x = minp;
  }
}

void addHeap(int x, int dist){
  hp[hpi] = x;
  dp[hpi] = dist;
  hpi ++;
  upHeap(x);
}
void removeHeap(){
  swap(hp[0], hp[hpi - 1]);
  swap(dp[0], dp[hpi - 1]);
  hpi --;
  dp[hpi] = MAXVAL;
  downHeap(0);
}

int main(){
  int n, m, a, b, c, i, j, dr, 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 < MAXN; i ++){
    dp[i] = MAXVAL;
    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");

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

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

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

  return 0;
}