#include <iostream>
#include <fstream>
#include <vector>
#define MAXN 50000
#define P(x) (x-1)/2
#define C1(x) x*2+1
#define C2(x) x*2+2

#define DEBUG 0

using namespace std;

struct Edge{
  int b, cost;

public:
  bool operator< (const Edge other){
    return this->cost < other.cost;
  }
  bool operator<= (const Edge other){
    return this->cost <= other.cost;
  }
};
vector<vector<Edge>> v;

int dist[MAXN];
Edge h[MAXN];
int dr = 0;

bool exists(int x){
  return x < dr;
}
bool isEmpty(){
  return dr == 0;
}

void upHeap(int x){
  if(x == 0)
    return;

  int p = P(x);
  if(h[x] < h[p])
    swap(h[p], h[x]);
  upHeap(p);
}

void downHeap(int x){
  int min;
  if(!exists(C1(x)) && !exists(C2(x)) || !exists(x)) 
    return;

  if(!exists(C1(x)))
    min = C2(x);
  else if(!exists(C1(x)))
    min = C1(x);

  else if(h[C2(x)] <= h[C1(x)])
    min = C2(x);
  else 
    min = C1(x);

  if(h[min] < h[x])
    swap(h[min], h[x]);
  downHeap(min);
}

void add(Edge val){
  h[dr] = val;
  dr ++;
  upHeap(dr - 1);
}
void remove(int id){
  if(dr == 0)
    return;

  h[id] = h[dr - 1];
  dr --;
  downHeap(id);
}

int main(){
  int n, m;

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

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

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

  while(v[0].size()){
    add(v[0].back());
    v[0].pop_back();
  }
  while(!isEmpty()){
    Edge e = h[0];
    if(DEBUG)
      printf("%d : %d\n", e.b + 1, e.cost);
    remove(0);

    if(dist[e.b] == -1){
      dist[e.b] = e.cost;
      while(v[e.b].size()){
        add({v[e.b].back().b, dist[e.b] + v[e.b].back().cost});
        v[e.b].pop_back();
      }
    }
  }

  ofstream fout ("dijkstra.out");
  for(int i = 1; i < n; i ++)
    fout << dist[i] << " ";
  fout << "\n";
  fout.close();

  return 0;
}