#include <fstream>
#include <vector>
#include <climits>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct Node{
		unsigned short node;
		short cost;
};
const int N_MAX = 5e4;
const int COST_MAX = 2e4;
const int HEAP_SIZE_MAX = N_MAX;
const int HEAP_VALUE_MAX = N_MAX - 1;
const unsigned short NOT_IN_HEAP = USHRT_MAX;
vector<Node> edge[N_MAX];
int dist[N_MAX]{};

class OptimizedHeap{
private:
		Node heap[HEAP_SIZE_MAX]{};
		unsigned short pos[HEAP_VALUE_MAX + 1]{};
		int heapSize = 0;

		bool (* cmp)(Node, Node);

		static const inline int parent(int node){
			return (node - 1) / 2;
		}

		static const inline int leftChild(int node){
			return 2 * node + 1;
		}

		static const inline int rightChild(int node){
			return 2 * node + 2;
		}

		void upHeap(int node){
			while(node && cmp(heap[node], heap[parent(node)])){
				swap(heap[node], heap[parent(node)]);
				pos[heap[node].node] = node;
				pos[heap[parent(node)].node] = parent(node);

				node = parent(node);
			}
		}

		void downHeap(int node){
			int smallest = node, left = leftChild(node), right = rightChild(node);

			if(left < heapSize && cmp(heap[left], heap[smallest]))
				smallest = left;
			if(right < heapSize && cmp(heap[right], heap[smallest]))
				smallest = right;

			if(smallest != node){
				swap(heap[smallest], heap[node]);
				pos[heap[node].node] = node;
				pos[heap[smallest].node] = smallest;

				downHeap(smallest);
			}
		}

public:

		OptimizedHeap(bool (* _cmp)(Node, Node)) : cmp(_cmp){
			for(int i = 0; i <= HEAP_VALUE_MAX; ++i)
				pos[i] = NOT_IN_HEAP;
		}

		void insert(Node x){
			if(inHeap(x.node))
				update(x.node, x.cost);
			else{
				heap[heapSize] = x;
				pos[x.node] = heapSize;
				++heapSize;

				upHeap(heapSize - 1);
			}
		}

		Node query(){
			return heap[0];
		}

		void extractRoot(){
			pos[heap[0].node] = NOT_IN_HEAP;
			swap(heap[0], heap[heapSize - 1]);
			pos[heap[0].node] = 0;
			--heapSize;
			downHeap(0);
		}

		void update(unsigned short node, short cost){
			if(cmp({node, cost}, heap[pos[node]]))
				heap[pos[node]].cost = cost;

			upHeap(pos[node]);
			downHeap(pos[node]);
		}

		bool empty(){
			return !heapSize;
		}

		bool inHeap(int node){
			return pos[node] != NOT_IN_HEAP;
		}
};

bool cmp(Node a, Node b){
	return a.cost < b.cost;
}

OptimizedHeap heap(cmp);

void Dijkstra(unsigned short start){
	for(int i = 0; i < N_MAX; ++i)
		dist[i] = N_MAX * COST_MAX + 1;

	heap.insert({start, 0});
	dist[start] = 0;

	while(!heap.empty()){
		int node = heap.query().node;
		heap.extractRoot();

		for(auto neighbour: edge[node])
			if(dist[neighbour.node] > dist[node] + neighbour.cost){
				dist[neighbour.node] = dist[node] + neighbour.cost;
				heap.insert(neighbour);
			}
	}

	for(int i = 0; i < N_MAX; ++i)
		if(dist[i] == N_MAX * COST_MAX + 1)
			dist[i] = 0;
}

int main(){
	int nodes, edges, u, v, w;
	fin >> nodes >> edges;
	for(int i = 0; i < edges; ++i){
		fin >> u >> v >> w;
		--u, --v;

		edge[u].push_back({v, w});
	}

	Dijkstra(0);

	for(int i = 1; i < nodes; ++i)
		fout << dist[i] << ' ';
	fout.put('\n');

	fin.close();
	fout.close();
	return 0;
}