#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;
const int Nmax = 50333;

vector<pii> G[Nmax];

int N, M, a, b, c, d[Nmax];
char vis[Nmax];

int main() {
  ifstream fin ("dijkstra.in");
  ofstream fout ("dijkstra.out");

  fin >> N >> M;
  for (int i = 0; i < M; ++i) {
    fin >> a >> b >> c;
    --a, --b;
    G[a].push_back({b, c});
  }
  for (int i = 1; i < N; ++i) {
    d[i] = INF;
  }

  priority_queue<pii, vector<pii>, greater<pii>> Q;
  d[0] = 0;
  Q.push({0, 0});
  while(!Q.empty()) {
    pii P = Q.top(); Q.pop();
    if (vis[P.second])
      continue;
    vis[P.second] = 1;
    for(pii X: G[P.second]) {
      if(vis[X.first] || d[X.first] <= d[P.second] + X.second)
        continue;
      d[X.first] = d[P.second] + X.second;
      Q.push({d[X.first], X.first});
    }
  }
  // d[0] = 0, vis[0] = 1;
  // for(pii P: G[0]){
  //   Q.push({P.second, P.first});
  // }

  // while(!Q.empty()) {
  //   pii P = Q.top(); Q.pop();
  //   if(vis[P.second])
  //     continue;
  //   vis[P.second] = 1;
  //   d[P.second] = P.first;
  //   for(pii X: G[P.second]) {
  //     if (vis[X.first] || d[X.first] <= d[P.second] + X.second)
  //       continue;
  //     d[X.first] = d[P.second] + X.second;
  //     Q.push({d[X.first], X.first});
  //   }
  // }
  for (int i = 1; i < N; ++i)
    fout << (d[i] == INF ? 0 : d[i]) << ' ';
  fout << endl;

  return 0;
}