#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMAX = 50000;

struct Node {
  int node, cost;

  bool operator < (const Node &temp) const {
    return cost > temp.cost;
  }
};

bool viz[NMAX + 2];
int dist[NMAX + 2];
vector <Node> v[NMAX + 2];
priority_queue <Node> pq;

void dijkstra() {
  dist[1] = 1;
  pq.push({1, 1});

  while (!pq.empty()) {
    int node = pq.top().node;
    int cost = pq.top().cost;
    pq.pop();

    if (!viz[node]) {
      viz[node] = 1;
      for (int i = 0; i < v[node].size(); ++i) {
        if (dist[v[node][i].node] > cost + v[node][i].cost) {
          dist[v[node][i].node] = cost + v[node][i].cost;
          pq.push({v[node][i].node, cost + v[node][i].cost});
        }
      }
    }
  }
}

int main() {
  int n, m, i, x, y, cost;

  fin >> n >> m;
  for (i = 1; i <= m; ++i) {
    fin >> x >> y >> cost;
    v[x].push_back({y, cost});
  }

  for (i = 1; i <= n; ++i)
    dist[i] = 1e9;
  dijkstra();
  for (i = 2; i <= n; ++i) {
    if (dist[i] == 1e9) dist[i] = 0;
    fout << dist[i] - 1 << " ";
  }
  return 0;
}