#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
FILE *fin = fopen("dijkstra.in", "r");
FILE *fout = fopen("dijkstra.out", "w");
//Graf dens -> matrice de adiacență - cost[][]
//const int MAX_N = 1000;
//const int MAX_M = (MAX_N * (MAX_N + 1)) / 2;
//Graf rar -> liste de adiacență - vector<int>
const int MAX_N = 50000;
const int MAX_M = 500000;
const int INF = 100000000;
int N, M, u, v, c;
struct Muchie {
int vecin;
int cost;
};
struct Nod {
int nod;
int cost;
bool operator < (const Nod &other) const {
return this->cost > other.cost;
}
};
vector<Muchie> vecini[1 + MAX_N];
bool vizitat[1 + MAX_N];
int cost[1 + MAX_N]; // adancime (in DFS si BFS)
int tata[1 + MAX_N]; // deUnde (pentru Dijkstra)
int main() {
fscanf(fin, "%d%d", &N, &M);
for (int i = 1; i <= M; i++) {
fscanf(fin, "%d%d%d", &u, &v, &c);
vecini[u].push_back(Muchie{v, c});
vecini[v].push_back(Muchie{u, c});
}
int start = 1;
// Dijkstra
priority_queue<Nod> frontiera;
for(int i = 1; i <= N; i++) {
cost[i] = INF;
}
cost[1]=0;
frontiera.push(Nod{start, 0});
while (!frontiera.empty()) {
int nod = frontiera.top().nod;
frontiera.pop();
if (!vizitat[nod]) {
vizitat[nod] = true;
for (Muchie m : vecini[nod]) {
if (cost[m.vecin] > cost[nod] + m.cost) {
cost[m.vecin] = cost[nod] + m.cost;
frontiera.push({m.vecin, cost[m.vecin]});
}
}
}
}
for(int i=2;i<=N;i++) fprintf(fout,"%d ", cost[i]);
return 0;
}