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

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

#define TII tuple<int, int, int>
#define PII pair<long long, long long>

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(make_pair(c, y));
  }

  priority_queue<PII, vector<PII>, greater<PII>> best;
  vector<long long> vis(n + 1, false), dist(n + 1, INT_MAX);
  dist[1] = 0;
  best.push(make_pair(0, 1));

  while (!best.empty())
  {
    auto curr = best.top();
    best.pop();
    vis[curr.second] = true;

    for (auto next : graph[curr.second])
      if (dist[next.second] > dist[curr.second] + next.first)
      {
        dist[next.second] = dist[curr.second] + next.first;
        if (!vis[next.second])
          best.push(make_pair(dist[next.second], next.second));
      }
  }

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

  return 0;
}