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

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

#define ll long long
#define pii pair<int, int>

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

  vector<vector<pii>> 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);
  priority_queue<pii, vector<pii>, greater<pii>> path;
  vector<bool> vis(n + 1, false);

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

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

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

    vis[curr.first] = true;

    for (pii &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;
}