#include <iostream>
#include <unordered_map>
#include <set>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
using namespace std;

#define INF 0xFFFFFFFFLL

struct Edge {
  int v, cost;
};

vector<Edge> edges[50500];
int64_t d[50500];

int n, m;

int main() {
  int a, b, c;
  freopen("dijkstra.in","r",stdin);
  freopen("dijkstra.out","w",stdout);

  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> a >> b >> c;
    edges[a].push_back({b, c});
  }

  for (int i = 1; i <= n; ++i) {
    d[i] = INF;
  }

  d[1] = 0;

  map<int,int> sorted_dist;
  sorted_dist.insert({0,1});
  while (!sorted_dist.empty()) {
    int x = sorted_dist.begin()->second;
    sorted_dist.erase(sorted_dist.begin());
    for (auto e : edges[x]) {
      int y = e.v;
      int cost = e.cost;
      if (d[y] > d[x] + cost) {
        d[y] = d[x] + cost;
        sorted_dist.insert({d[y],y});
      }    
    }
  }

  for (int i = 1; i <= n; ++i) {
    if (d[i] == INF) { cout << "0 "; } else cout << d[i] << " ";
  }

  return 0;
}