#include <iostream>
#include <vector>
#include <fstream>
#include <set>
#include <climits>
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;
set<pair<int, int>> pq;
pq.insert({0, s});
while(pq.size() > 0){
int dist_curenta = pq.begin()->first;
int nod_curent = pq.begin()->second;
pq.erase(pq.begin());
for(auto muchie : v[nod_curent]){
int vecin = muchie.first;
int cost = muchie.second;
if(dist_curenta + cost < dist[vecin]){
if(dist[vecin] != INT_MAX){
pq.erase({dist[vecin], vecin});
}
dist[vecin] = dist_curenta + cost;
pq.insert({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;
}