#include<bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct muchie{
int x, c;
};
const int N = 50002;
vector<muchie> g[N];
int dist[N], viz[N], nrViz[N], n, m;
struct cmp{
public :
bool operator() (muchie &a, muchie &b){
if(a.c > b.c)
return true;
return false;
}
};
priority_queue<muchie, vector<muchie>, cmp> H;
int main(){
int i, j, x, y, c;
fin >> n >> m;
for(i=1;i<=m;i++){
fin >> x >> y >> c;
g[x].push_back({y, c});
}
for(i=2;i<=n;i++)
dist[i] = INT_MAX;
H.push({1, 0});
while(!H.empty()){
muchie e = H.top();
int nod = e.x;
int cost = e.c;
H.pop();
if(viz[nod])
continue;
viz[nod] = 1;
for(muchie vecin : g[nod]){
if(!viz[vecin.x] && dist[vecin.x] > cost + vecin.c){
dist[vecin.x] = vecin.c + cost;
H.push({vecin.x, dist[vecin.x]});
}
}
}
for(i=2;i<=n;i++)
if(dist[i] == INT_MAX)
fout << "0 ";
else
fout << dist[i] << " ";
}