#include <cstdio>
#include <vector>
#include <algorithm>
#include <memory>
#include <queue>

using namespace std;


class Solver{
private:
  const int INF = 0x3f3f3f3f;
  int N, M;
public:
  Solver() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
  }
  ~Solver() {
    fclose(stdin);
    fclose(stdout);
  }
  void readData() {
    scanf("%d%d", &N, &M);
    vector<vector<pair<int,int>>> Graph;
    Graph.resize(N);
    int from, to, cost;
    for (int i = 0; i < M; ++i) {
      scanf("%d%d%d", &from, &to, &cost);
      --from; --to;
      Graph[from].emplace_back(to, cost);
    }
    computeMinPaths(Graph);
  }

  void dijkstra(int k, const vector<vector<pair<int,int>>>& Graph, vector<int> &paths) {
    vector<int> DP((int)Graph.size(), INF);
    DP[k] = 0;

    priority_queue<pair<int,int>> pq;
    pq.emplace(-DP[k], k);

    int cost, v, kvCost;
    while (!pq.empty()) {
      tie(cost, k) = pq.top(); pq.pop();
      cost *= -1;


      if (DP[k] != cost)
	continue;

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

  void computeMinPaths(const vector<vector<pair<int,int>>>& Graph) {
    vector<int> paths;
    dijkstra(0, Graph, paths);
    for (auto it: paths)
      if (it >= INF)
	printf("0 ");
      else
	printf("%d ", it);
    printf("\n");
  }
};

int main() {
  unique_ptr<Solver> s = make_unique<Solver>();

  s->readData();
 
  return 0;
}