#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int oo = 2000000000;
const int NMAX = 50005;
typedef pair<int, int> p;
int N, M, D[NMAX];
vector <p> G[NMAX];

struct Node{
  int index, value;

  Node(int ind, int val){
    index = ind;
    value = val;
  }

  bool operator<(const Node &other)const{
    return (value > other.value);
  }
};

priority_queue <Node> q;

void Read(){
  in >> N >> M;
  for(int i = 1; i <= M; ++i){
    int a, b, c;
    in >> a >> b >> c;
    G[a].push_back(make_pair(b, c));
  }
}

void Solve(){
  for(int i = 2; i <= N; ++i)
    D[i] = oo;
  q.push(Node(1, 0));
  while(!q.empty()){
    Node top = q.top();
    q.pop();
    if(top.value != D[top.index])
      continue;
    for(int i = 0; i < G[top.index].size(); ++i){
      p neighbour = G[top.index][i];
      if(D[neighbour.first] > D[top.index] + neighbour.second){
        D[neighbour.first]  = D[top.index] + neighbour.second;
        q.push(Node(neighbour.first, D[neighbour.first]));
      }
    }
  }
}

void Print(){
  for(int i = 2; i <= N; ++i)
    out << (D[i] != oo ? D[i] : 0) << " ";
  out << "\n";
}

int main(){
  Read();
  Solve();
  Print();
  return 0;
}