#include <cstdio>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

vector<vector<pair<int, int>>> Graph;
vector<int> DP;
priority_queue<pair<int, int>> Q;

int main()
{
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  int N, M;
  scanf("%d%d", &N, &M);
  Graph.resize(N);
  
  for (int i = 1; i <= M; ++i) {
    int a, b, cost;
    scanf("%d%d%d", &a, &b, &cost);
    Graph[a - 1].emplace_back(cost, b - 1);
  }

  DP.resize(N);
  fill(DP.begin(), DP.end(), 0x3f3f3f3f);

  int k = 0; // start node
  int crtCost = 0; // current cost;
  DP[k] = crtCost;

  Q.emplace(-DP[k], k);
  while (!Q.empty()) {
    tie(crtCost, k) = Q.top(); Q.pop();
    crtCost *= -1;
    if (DP[k] > crtCost)
      continue;

    int vCost, v;
    for (auto it : Graph[k]) {
      tie(vCost, v) = it;
      if (DP[v] > DP[k] + vCost) {
	DP[v] = DP[k] + vCost;
	Q.emplace(-DP[v], v);
      }
    }
  }

  for (int i = 1; i < DP.size(); ++i)
    if (DP[i] >= 0x3f3f3f3f)
      printf("0 ");
    else
      printf("%d ", DP[i]);
  return 0;
}