#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define NMAX 50005
#define INF ((1<<30)-1)
int n, m, d[NMAX], prec[NMAX];
bool viz[NMAX];
vector<pair<int, int>> G[NMAX];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
void citire() {
f >> n >> m;
int a, b, c;
for (int i = 1; i <= m; ++i) {
f >> a >> b >> c;
G[a].push_back({b, c});
}
}
void initializare() {
for (int i = 1; i <= n; ++i)
d[i] = INF;
}
void vizitare_nod(int x) {
viz[x] = true;
for (auto &nod: G[x])
if (d[x] + nod.second < d[nod.first]) {
d[nod.first] = d[x] + nod.second;
q.push({d[nod.first], nod.first});
}
}
void dijkstra() {
d[1] = 0;
q.push({0, 1});
while (!q.empty()) {
int nod = q.top().second;
q.pop();
if (viz[nod])
continue;
vizitare_nod(nod);
}
}
void afisare() {
for (int i = 2; i <= n; ++i) {
if (d[i] == INF)
g << 0 << ' ';
else
g << d[i] << ' ';
}
}
int main() {
citire();
initializare();
dijkstra();
afisare();
return 0;
}