#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
 
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct node{
  int n;
  int cost;

  bool operator < (const node& other) const {
    return this->cost <= other.cost;
  }

  bool operator > (const node& other) const {
    return this->cost > other.cost;
  }

};

int minDistance[50005];
int viz[50005];

node pQueue[50001];
int len = -1;

void push(node n);
node pop();

vector<node> G[50005];

int n, m;

void dijkstra();

int main(){
  
  in>>n>>m;

  for(int i = 1; i <= n; i+=3){
    minDistance[i] = 90000;
    minDistance[i + 1] = 90000;
    minDistance[i + 2] = 90000;
  }

  int x, y, cost;
  for(int i = 1; i <= m; i++){
    in>>x>>y>>cost;
    G[x].push_back({y, cost});
  }

  dijkstra();

  for(int i = 2; i <= n; i++){
    if(viz[i])
      out<<minDistance[i]<<" ";
    else out<<0<<" ";
  }

  return 0;
}

void dijkstra(){
  node start = {1, 0};
  minDistance[1] = 0;
  push(start);

  while(len >= 0){
    node temp = pop();
    int n = temp.n;
    viz[n] = true;

    short len = G[n].size();

    for(short i = 0; i < len; i++){
      node desc = G[n].at(i);

      int d = desc.n;

      if(!viz[d]){
        if(minDistance[n] + desc.cost < minDistance[d]){
          minDistance[d] = minDistance[n] + desc.cost;
        }

        push({d, minDistance[d]});

      }

    }
  }
}
 
void push(node n){

  pQueue[++len] = n;

  int k = len;

  bool heap = false;
  while(k > 0 && !heap){

    int parent = (k - 1) / 2;

    if(pQueue[k] < pQueue[parent]){
      swap(pQueue[k], pQueue[parent]);
      k = parent;
    } else {
      heap = true;
    }

  }

}
node pop(){
  node extras = pQueue[0];
  swap(pQueue[0], pQueue[len]);
  node* nm = new node;
  pQueue[len] = *nm;
  len--;
  
  int k = 0;

  bool heap = false;
  while(2* k + 1 < len && !heap){
    int des = 2 * k + 1;

    if(pQueue[des] > pQueue[des + 1]){
      des++;
    }

    if(pQueue[k] > pQueue[des]){
      swap(pQueue[k], pQueue[des]);
      k = des;
    } else {
      heap = true;
    }

  }

  return extras;
}