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

using namespace std;

struct Edge{
  int a;
  int b;
  int cost;
public:
  int getOther(int id){
    if(id == a)
      return b;
    return a;
  }
};

vector<vector<int>> v;
Edge edges[MAXN];
int c[MAXN], d[MAXN], f[MAXN];

int main(){
  int n, a, b, cost, i, st, dr, m;

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

  for(i = 0; i < m; i ++){
    fin >> a >> b >> cost;
    a --;
    b --;

    edges[i] = {a, b, cost};
    v[a].push_back(i);
    v[b].push_back(i);
  }
  fin.close();

  st = 0;
  dr = 1;
  c[0] = 0;
  d[0] = 0;

  for(i = 0; i < n; i ++)
    f[i] = -1;
  f[0] = 0;

  while(st < dr){
    int id = c[st];
    int dist = d[st];
    st ++;

    for(i = 0; i < v[id].size(); i ++){
      Edge ex = edges[v[id][i]];
      int other = ex.getOther(id);

      if(f[other] == -1){ // Daca nu am mai fost in nodul celalalt
        int drj = dr;
        f[other] = dist + ex.cost;

        while(drj > st && dist + ex.cost < d[drj - 1]){
          c[drj] = c[drj - 1];
          d[drj] = d[drj - 1];
          drj --;
        }
        c[drj] = ex.getOther(id);
        d[drj] = dist + ex.cost;
        dr ++;
      }
    }
  }

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