#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <set>
#include <climits>
using namespace std;
ifstream be("dijkstra.in");
ofstream ki("dijkstra.out");
void beolvas(vector<vector<pair<int, int>>> &graf, int m);
void legrovidebb_ut(const vector<vector<pair<int, int>>>& graf, int n, int start);
void dijkstra(const vector<vector<pair<int, int>>>& graf, int n, int start, vector<int>& d, vector<int>& p);
void relax(const vector<vector<pair<int, int>>>& graf, int v, vector<int>& d, vector<int>& p, priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>> >& ismeretlen);
//void dijkstra_ut(int v, vector<int>& d, vector<int>& p);
int main() {
int n, m, start;
be >> n >> m;
start = 0;
//be >> n >> m >> start;
//start--;
vector<vector<pair<int,int>>> graf(n);
beolvas(graf, m);
legrovidebb_ut(graf, n, start);
}
void beolvas(vector<vector<pair<int, int>>>& graf, int m) {
for (int i = 0; i < m; i++) {
int x, y, z;
be >> x >> y >> z;
graf[x-1].push_back(make_pair((y-1), z));
}
}
void legrovidebb_ut(const vector<vector<pair<int, int>>>& graf, int n, int start) {
vector<int> d(n, -1);
vector<int> p(n, -1);
dijkstra(graf, n, start, d, p);
for (int i = 1; i < n; i++) {
ki << d[i] << " ";
}
/*for (int i = 0; i < n; i++) {
if (i != start) {
if (d[i] != INT_MAX) {
ki << "A legrovidebb ut hossza " << i+1 << "-ba/be: " << d[i] << "\n";
ki << "A legrovidebb ut " << i+1 << "-ba/be: ";
dijkstra_ut(i, d, p);
}
else {
ki << "A legrovidebb ut hossza " << i+1 << "-ba/be: Nem lehet eljutni!" << "\n";
ki << "A legrovidebb ut " << i+1 << "-ba/be: Nem lehet eljutni!" << "\n";
}
}
}*/
}
void dijkstra(const vector<vector<pair<int, int>>>& graf, int n, int start, vector<int>& d, vector<int>& p) {
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>> > ismeretlen;
for (int i = 0; i < n; i++) {
d[i] = INT_MAX;
}
d[start] = 0;
ismeretlen.push({ 0,start });
while (!ismeretlen.empty()) {
auto best = ismeretlen.top();
int du = best.first;
int u = best.second;
ismeretlen.pop();
if (du != d[u]) continue;
if (d[u] != INT_MAX)
relax(graf, u, d, p, ismeretlen);
}
}
void relax(const vector<vector<pair<int, int>>>& graf, int v, vector<int>& d, vector<int>& p, priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>> >&ismeretlen) {
for (auto i : graf[v]) {
int w = i.first;
if ((d[v] != INT_MAX) && (d[w] > (d[v] + i.second))) {
d[w] = d[v] + i.second;
p[w] = v;
ismeretlen.push({ d[w],w });
}
}
}
/*void dijkstra_ut(int v, vector<int>& d, vector<int>& p) {
int k = d[v];
vector<int> ut;
ut.push_back(v);
while (k > 0 && p[ut[ut.size() - 1]]!=-1) {
ut.push_back(p[ut[ut.size() - 1]]);
k-=d[ut[ut.size() - 1]];
}
for (int i = ut.size() - 1; i >= 0; i--) {
ki << ut[i]+1 << " ";
}
ki << "\n";
}*/