#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
const int INF = 2e9;
const int NMAX = 50005;
vector<pair<int, int>> adj[NMAX];
int d[NMAX];
void dijkstra(int start, int n) {
for (int i = 1; i <= n; i++) {
d[i] = INF;
}
d[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
auto [cost, u] = pq.top();
pq.pop();
if (cost > d[u]) continue;
for (auto& edge : adj[u]) {
int v = edge.first;
int c = edge.second;
if (d[u] + c < d[v]) {
d[v] = d[u] + c;
pq.push({d[v], v});
}
}
}
}
int main() {
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m;
f >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, c;
f >> u >> v >> c;
adj[u].push_back({v, c});
}
dijkstra(1, n);
for (int i = 2; i <= n; i++) {
if (d[i] == INF) {
g << 0 << " ";
} else {
g << d[i] << " ";
}
}
g << "\n";
return 0;
}