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

struct node{
  int n;
  int cost;

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

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

};

int minDistance[50005];
int viz[50005];
vector<node> G[50005];
set<node> s;

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;
  s.insert(start);

  while(!s.empty()){
    node temp = *s.begin();
    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;
        }

        s.insert({d, minDistance[d]});

      }

    }
    s.erase(s.begin());
  }
}