#include <bits/stdc++.h>

const int MAX_N = 5e4 + 5;
const int MY_INT_MAX = 1e9;

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

class PrqStr {
  public:
    int pos;
    int val;
    bool operator<(const PrqStr &other) const {
      return val < other.val;
    }
};

class Edge {
  public:
    int pos;
    int cost;
};

std::vector<Edge> web[MAX_N];

std::priority_queue<PrqStr> prq;
int dist[MAX_N];

void dijkstra(int start, int n) {
  PrqStr u;

  while (!prq.empty()) {
    u = prq.top();
    prq.pop();

    for (auto i : web[u.pos]) {
      if (dist[u.pos] + i.cost < dist[i.pos]) {
        prq.push({i.pos, dist[u.pos] + i.cost});
        dist[i.pos] = dist[u.pos] + i.cost;
      }
    }
  }
}

int main() {
  int n, p, i, j, c;

  fin >> n >> p;

  while (p--) {
    fin >> i >> j >> c;
    web[i].push_back({j, c});
  }

  for (i = 1; i <= n; i++)
    if (i != 1)
      dist[i] = MY_INT_MAX;
  prq.push({1, dist[1]});

  dijkstra(1, n);

  for (i = 2; i <= n; i++) {
    if (dist[i] == MY_INT_MAX)
      fout << -1;
    else
      fout << dist[i];
    fout << ' ';
  }

  return 0;
}