#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]);
			swap(ph[h[i]],ph[h[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-1)/2]]) {
			swap(h[i], h[(i-1)/2]);
			swap(ph[h[i]],ph[h[(i-1)/2]]);
			i = (i-1)/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;
}