#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4 + 5;

int n, m;
vector<pair<int, int>> g[NMAX];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int dist[NMAX];
bool used[NMAX];

void solve() {
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, c;
    fin >> u >> v >> c;
    g[u].push_back(make_pair(v, c));
  }
  for (int i = 2; i <= n; i++)
    dist[i] = 2e9;
  pq.push(make_pair(0, 1));
  while (!pq.empty()) {
    pair<int, int> top = pq.top();
    pq.pop();
    int node = top.second;
    int cost = top.first;
    if (used[node])
      continue;
    used[node] = true;
    for (auto it : g[node])
      if (dist[it.first] > cost + it.second) {
        dist[it.first] = cost + it.second;
        pq.push(make_pair(dist[it.first], it.first));
      }
  }
  for (int i = 2; i <= n; i++) {
    if (dist[i] == 2e9)
      fout << 0 << ' ';
    else fout << dist[i] << ' ';
  }
}

int main() {
  ios_base :: sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}