#include <bits/stdc++.h>
using namespace std;

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

#define LL long long
#define PLL pair<LL, LL>
#define INF LONG_LONG_MAX

int main()
{
  int n, m;
  fin >> n >> m;

  vector<vector<PLL>> graph(n + 1);
  for (int i = 1; i <= m; i++)
  {
    int x, y, c;
    fin >> x >> y >> c;
    graph[x].push_back({y, c});
  }

  vector<LL> dist(n + 1, INT_MAX);

  static auto compFunc = [&](PLL &p1, PLL &p2)
  {
    return (p1.second >= p2.second);
  };

  priority_queue<PLL, vector<PLL>, function<bool(PLL &, PLL &)>> path(compFunc);
  vector<bool> vis(n + 1, false);

  dist[1] = 0;
  path.push({1, 0});

  while (!path.empty())
  {
    PLL curr = path.top();
    path.pop();

    if (vis[curr.first] == true)
      continue;

    vis[curr.first] = true;

    for (PLL &next : graph[curr.first])
      if (next.second + dist[curr.first] < dist[next.first])
        dist[next.first] = dist[curr.first] + next.second, path.push({next.first, dist[next.first]});
  }

  for (int i = 2; i <= n; i++)
  {
    if (dist[i] == INT_MAX)
      dist[i] = 0;
    fout << dist[i] << " ";
  }

  return 0;
}