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

#define INF 0x77359400

struct Edge {
  int v, cost;
};

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

int n, m;

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

  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; ++i) {
    scanf("%d %d %d", &a, &b, &c);
    edges[a].push_back({b, c});
  }

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

  d[1] = 0;

  set<pair<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) {
        auto it = sorted_dist.find({d[y],y});
        if (it != sorted_dist.end()) {
          sorted_dist.erase(it); 
        }
        d[y] = d[x] + cost;
        sorted_dist.insert({d[y],y});
      }    
    }
  }

  for (int i = 2; i <= n; ++i) {
    if (d[i] == INF) printf("0 "); else printf("%d ", (int)d[i]);
  }

  return 0;
}