#include <fstream>
#include <vector> 
#include <queue>
#include <limits>  
#define nm 50001 
 
using namespace std; 

vector< pair<int, int> > W[nm]; 
priority_queue<int> Q; 
int N; 

int main() { 
int x, y, l, M, i; 
vector< pair<int, int> >::iterator t; 
int D[nm]; 
ifstream fin("dijkstra.in"); 
ofstream fout("dijkstra.out"); 
fin >> N >> M; 

while (M--) { 
fin >> x >> y >> l; 

W[x].push_back(pair<int, int>(y, l)); 
} 
fill(D, D + N + 1, INT_MAX); 
D[1] = 0; 

Q.push(1); 

 

// put into set 

while (!Q.empty()) { 

 

// get min 

int s = Q.top(); 

Q.pop(); 

//I[s] = false; 

 

// iterate neighbors 

for (t = W[s].begin(); t != W[s].end(); ++t) { 

x = t->first; 

y = t->second; 

 

if (D[x] > D[s] + y) { 

 

D[x] = D[s] + y; 

 

//if (!I[x]) { 

Q.push(x); 

//I[x] = true; 

//} 

 

} 

} 

 

} 

 

// write dists 

for (i = 2; i <= N; ++i) { 

fout << (D[i] == INT_MAX? 0: D[i]) << ' '; 

} 

 

fout << '\n'; 

 

fin.close(); 

fout.close(); 

 

return 0; }