#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector<int> tata;
vector<int> dist;
vector<vector<pair<int, int>>> v;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
void dijkstra(int src){
dist[src] = 0;
pq.push({0, src});
while(!pq.empty()){
int d = pq.top().first;
int n = pq.top().second;
pq.pop();
if(d > dist[n]){
continue;
}
for(auto muchie:v[n]){
int nod = muchie.first;
int cost = muchie.second;
if(dist[n] + cost < dist[nod]){
dist[nod] = dist[n] + cost;
pq.push({dist[nod], nod});
}
}
}
}
int main(){
int x, y, p, n, m;
fin>>n>>m;
dist.assign(n+1, 20001);
tata.assign(n+1, 0);
v.resize(n+1);
for(int i=0; i<m; i++){
fin>>x>>y>>p;
v[x].push_back({y, p});
}
dijkstra(1);
for(int i=2; i<=n; i++){
fout<<dist[i]<<' ';
}
return 0;
}