#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int nmax = 50005;
int extractMin(unordered_set<int> s, int* dMin, int N){
int mini = INT_MAX;
int poz = - 1;
for(int i = 1; i <= N; ++i)
if(s.find(i) == s.end() && dMin[i] < mini){
mini = dMin[i];
poz = i;
}
return poz;
}
int main()
{ int N, M;
unordered_set<int> s;
vector <pair<int, int>> adj[nmax];
int dMin[nmax];
fin >> N >> M;
for(int k = 0; k < M; ++k){
int i, j, cost;
fin >> i >> j >> cost;
adj[i].push_back(make_pair(j, cost));
}
dMin[1] = 0;
for(int i = 2; i <= N; ++i)
dMin[i] = (INT_MAX) / 2;
int crt = extractMin(s, dMin, N);
for(;crt != -1;){
s.insert(crt);
for(int i = 0; i < adj[crt].size(); ++i){
if(dMin[crt] != INT_MAX && dMin[crt] + adj[crt][i].second < dMin[adj[crt][i].first])
dMin[adj[crt][i].first] = dMin[crt] + adj[crt][i].second;
}
crt = extractMin(s, dMin, N);
}
for(int i = 2; i <= N; ++i)
if(dMin[i] != INT_MAX)
fout << dMin[i] << ' ';
else fout << 0 << ' ';
return 0;
}