#define maxs(a, b) a = (a > b) ? a : b
#define mins(a, b) a = (a < b) ? a : b

#define all(a) a.begin(), a.end()
#define rng(a, i, j) a.begin() + i, a.begin() + j

#define aall(a, n) a + 1, a + 1 + n
#define arng(a, i, j) a + i, a + j

#define pb push_back
#define ins insert
#define sz(a) (int)a.size()

#define r inFile
#define w outFile
#define wd std::cout

#define wln(a) inFile << (a) << '\n';
#define wsp(a) outFile << (a) << ' ';

#include <fstream>
#include <iostream>
#include <queue>
#include <vector>

std::ifstream inFile("dijkstra.in");
std::ofstream outFile("dijkstra.out");

const int NMAX = 5e4;

struct Edge {
  int node;
  int cost;

  Edge() = default;

  Edge(int node, int cost) : node(node), cost(cost){};
};

struct QElement {
  int node;
  int c_dist;

  QElement() = default;

  QElement(int node, int c_dist) : node(node), c_dist(c_dist){};

  bool operator<(const QElement& other) const {
    return this->c_dist < other.c_dist;
  }
};

std::vector<Edge> graph[1 + NMAX];

int dist[1 + NMAX];
std::priority_queue<QElement> pq;

void dijkstra(int src) {
  dist[src] = 1;
  pq.emplace(src, 1);

  while (!pq.empty()) {
    QElement front = pq.top();
    pq.pop();

    if (front.c_dist > dist[front.node]) {
      continue;
    }

    for (Edge& edge : graph[front.node]) {
      int new_dist = front.c_dist + edge.cost;

      if (dist[edge.node] == 0 || dist[edge.node] > new_dist) {
        dist[edge.node] = new_dist;
        pq.emplace(edge.node, new_dist);
      }
    }
  }
}

int main() {
  int n, m;
  r >> n >> m;

  while (m--) {
    int a, b, c;
    r >> a >> b >> c;

    graph[a].emplace_back(b, c);
  }

  for (int i = 1; i <= n; ++i) {
    dist[i] = 0;
  }

  dijkstra(1);

  for (int i = 2; i <= n; ++i) {
    w << dist[i] - 1 << ' ';
  }

  return 0;
}