#include <bits/stdc++.h>
#define MAXN 50005
#define PlusINF (1LL << 30)
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"

using namespace std;

vector<pair<int, int>> Graph[MAXN];
set<pair<int, int>> s;
bool visited[MAXN];

int distMin[MAXN];
int nodes, edges;

void read_graph() {
  int x,
      y,
      c;

  freopen(FIN, "r", stdin);
  scanf("%d %d", &nodes, &edges);

  for (int edge = 1; edge <= edges; ++edge) {
    scanf("%d %d %d", &x, &y, &c);
    Graph[x].push_back({ c, y });
  }
}

void dijkstra() {
  distMin[1] = 0;

  s.insert({ 0, 1 });

  while(!s.empty()) {
    set<pair<int, int>> :: iterator it = s.begin();

    int node = it -> second;
    s.erase( it );

    if (visited[node]) continue;
    visited[node] = 1;

    for (int i = 0; i < Graph[node].size(); ++i) {
      int x = Graph[node][i].second;
      int c = Graph[node][i].first;

      if (!visited[x] && distMin[node] + c < distMin[x]) {
        distMin[x] = distMin[node] + c;
        s.insert({ distMin[x], x });
      }
    }
  }
}

void write_data() {
  // distMin
  freopen(FOUT, "w", stdout);

  for (int i = 2; i <= nodes; i++) printf("%d ", (distMin[i] < PlusINF) ? distMin[i] : 0);
}

int main() {

  read_graph();
  // display_graph();
  // display_costs();

  dijkstra();
  write_data();

  return 0;
}