#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
#define INT_MAX 2147483647
using namespace std;

ifstream in("dijkstra.in"); 
ofstream out("dijkstra.out");

struct nod{
  int index, cost;
  bool operator<(const nod& a) const{
    return cost > a.cost;
  }
};

priority_queue<nod> pq;
vector<nod> w[50001];
int cost[50001];
bool visited[50001];

void Dijkstra(){
  while(pq.empty() == false){
    int vertex = pq.top().index;
    int c = pq.top().cost;
    if(visited[vertex] == true) continue;
    pq.pop();
    for(auto it : w[vertex]){
      if(c + it.cost < cost[it.index]){
        cost[it.index] = c+ it.cost;
        pq.push(it);
      }
    }
  }
}

int main(){
  int N, M;
  in >> N >> M;

  for(int i = 1; i<=N; i++)
  {
    cost[i] = INT_MAX;
    visited[i] = false;
  }
  for(int k = 0; k<M; k++){
    int i, j, dist;
    in >> i >> j >> dist;
    w[i].push_back({j, dist});
  }
  nod start({1, 0});
  pq.push(start);
  Dijkstra();
  for(int i = 2; i<=N; i++) out << cost[i] << " "; 
  return 0;
}