#include <vector>
#define oo (1<<30)
template <typename T>
void swap(T &x, T &y) {
T aux = x;
x = y;
y = aux;
}
class MinHeap {
std::vector <unsigned int> h;
std::vector <unsigned int> keys;
std::vector <int> ph;
void sift(unsigned int i) {
unsigned int s1, s2, best = i;
s1 = 2*i+1;
s2 = 2*i+2;
if(s1 < h.size() && keys[h[best]] > keys[h[s1]])
best = s1;
if(s2 < h.size() && keys[h[best]] > keys[h[s2]])
best = s2;
if(best != i) {
swap(h[i], h[best]);
ph[h[i]]=i;
ph[h[best]]=best;
sift(best);
}
}
public:
MinHeap(unsigned int n, unsigned int root): keys(n+1, oo), ph(n+1, -1) {
for(unsigned int i = 1; i <= n; i++) {
h.push_back(i);
ph[i] = i-1;
}
keys[root] = 0;
/*for(int i = h.size()/2; i>=0; i--)
sift(i);*/
}
bool empty() {
return (h.size() == 0);
}
unsigned int getKey(unsigned int v) {
return keys[v];
}
unsigned int get() {
unsigned int temp = h[0];
ph[h[0]] = -1;
h[0] = h[h.size()-1];
ph[h[0]] = 0;
h.pop_back();
sift(0);
return temp;
}
void setKey (unsigned int v, unsigned int key) {
int i = ph[v];
keys[v] = key;
while(i>0 && keys[h[i]]<keys[h[i/2]]) {
swap(h[i], h[i/2]);
ph[h[i]]=i;
ph[h[i/2]]=i/2;
i/=2;
}
}
};
class Graph {
unsigned int size;
std::vector <std::pair<unsigned int, unsigned int> > *v;
public:
Graph(unsigned int n): size(n) {
v = new std::vector <std::pair<unsigned int, unsigned int> > [n+1];
}
void addEdge(unsigned int i, unsigned int j, unsigned int len) {
v[i].push_back(std::make_pair(j,len));
}
void Dijkstra(unsigned int root, void (*proc)(unsigned int)) {
MinHeap h(size, root);
unsigned int x, y, l;
while(!h.empty()) {
x = h.get();
for(int i=0; i<v[x].size(); i++) {
y = v[x][i].first, l = v[x][i].second;
if(h.getKey(x) + l < h.getKey(y))
h.setKey(y, h.getKey(x)+l);
}
}
for(unsigned int i=1; i<=size; i++)
if(i!=root) proc(h.getKey(i));
}
};
#include <fstream>
std::ifstream f("dijkstra.in");
std::ofstream g("dijkstra.out");
void print(unsigned int x) {
if(x == oo)
g<<0<<' ';
else
g<<x<<' ';
}
int main()
{
int n, m, x, y, l;
f>>n>>m;
Graph G(n);
while(m--) {
f>>x>>y>>l;
G.addEdge(x,y,l);
}
G.Dijkstra(1, print);
return 0;
}