#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int NMax = 50005;
int N, M;
vector<int> D(NMax, INT_MAX);
vector<bool> InCoada(NMax);
vector < pair <int, int> > G[NMax];
struct comparaDistante{
bool operator()(int x, int y){
return D[x] > D[y];
}
};
priority_queue <int, vector<int>, comparaDistante> Coada;
void Citeste(){
fin >> N >> M;
for(int i = 1; i <= M; i++){
int x, y, c;
fin >> x >> y >> c;
G[x].push_back(make_pair(y, c));
}
}
void Afiseaza(){
for(int i = 2; i <= N; i++){
if(D[i] != INT_MAX)
fout << D[i] << " ";
else
fout << "0 ";
}
}
void Dijkstra(int nodStart){
D[nodStart] = 0;
Coada.push(nodStart);
InCoada[nodStart] = true;
while(!Coada.empty()){
int nodCurent = Coada.top();
Coada.pop();
InCoada[nodCurent] = false;
for(unsigned int i = 0; i < G[nodCurent].size(); i++){
int Vecin = G[nodCurent][i].first;
int Cost = G[nodCurent][i].second;
if(D[nodCurent] + Cost < D[Vecin]){
D[Vecin] = D[nodCurent] + Cost;
if(InCoada[Vecin] == false){
Coada.push(Vecin);
InCoada[Vecin] = true;
}
}
}
}
}
int main(){
Citeste();
Dijkstra(1);
Afiseaza();
return 0;
}