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

using namespace std;

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

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

int main(){
  long long 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);
  }
  fin.close();

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

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

    if(f[id] == 0){
      f[id] = 1;
      r[id] = dist;

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

        if(!f[other]){ // Daca nu am mai fost in nodul celalalt
          int drj = dr;

          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 << r[i] << " ";
  }
  fout << endl;
  fin.close();
  return 0;
}