#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(make_pair(b, c));
  }
  for (int i = 1; i < N; ++i) {
    d[i] = INF;
  }

  priority_queue<pii, vector<pii>, greater<pii> > Q;
  d[0] = 0, vis[0] = 1;
  for(pii P: G[0]){
    Q.push(make_pair(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(make_pair(d[X.first], X.first));
    }
  }
  for (int i = 1; i < N; ++i)
    fout << d[i] << ' ';
  fout << endl;

  return 0;
}