#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

const int MAX = (5e4 + 5);
const int INF = (1e9);

int main() {
  priority_queue < pair < int, int > > h;
  vector < vector < pair < int, int > > > node(MAX);
  vector < int > dist(MAX, -INF);
  int n, m;
  cin >> n >> m;

  for (int i = 1; i <= m; i ++) {
    int a, b, cost;
    cin >> a >> b >> cost;
    node[a].push_back({-cost, b});
  }

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

  while (!h.empty()) {
    pair < int, int > cur = h.top();
    int cur_dist = cur.first;
    int cur_node = cur.second;
    h.pop();
    if (dist[cur_node] != cur_dist) {
      continue;
    }

    for (auto x : node[cur_node]) {
      if (cur_dist + x.first > dist[x.second]) {
        dist[x.second] = cur_dist + x.first;
        h.push({dist[x.second], x.second});
      }
    }
  }

  for (int i = 2; i <= n; i ++) {
    if (dist[i] == INF)
      cout << 0 << ' ';
    else 
      cout << -dist[i] << ' ';
  }

  cout << '\n';
}