#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
int main(){
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m;
f >> n >> m;
vector<vector<pair<int, int>>> v(n + 1);
for (int i = 0; i < m; i++) {
int a, b, c;
f >> a >> b >> c;
v[a].push_back({b, c});
}
int s = 1;
vector <int> dist(n + 1, INT_MAX);
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, s});
while(pq.size() > 0){
int dist_curenta = pq.top().first;
int nod_curent = pq.top().second;
pq.pop();
if (dist_curenta > dist[nod_curent]) {
continue;
}
for( auto muchie : v[nod_curent]){
int vecin = muchie.first;
int cost = muchie.second;
if(dist_curenta + cost < dist[vecin]){
dist[vecin] = dist_curenta + cost;
pq.push({dist[vecin], vecin});
}
}
}
for(int i = 1; i <= n; i++){
if(i == s) continue;
if(dist[i] == INT_MAX)
g << "0 ";
else
g << dist[i] << " ";
}
return 0;
}