// infoarenaDFSnonRec.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include <fstream>
#include <vector>
#include <utility>

#define MaxN 50005
#define INF 123456789

using namespace std;

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

int N, M;
int heapSize;
int heap[MaxN], dist[MaxN];
int nodeToIndex[MaxN];
vector<pair<int, int>> G[MaxN];


void heapswap(int x, int y) {
	int temp = heap[x];
	heap[x] = heap[y];
	heap[y] = temp;
}

void pushDown(int index) {
	int minIndex = index;
	if (2 * index <= heapSize && dist[heap[2 * index]] < dist[heap[index]])
		minIndex = 2 * index;
	if (2 * index + 1 <= heapSize && dist[heap[2 * index + 1]] < dist[heap[minIndex]])
		minIndex = 2 * index + 1;

	if (minIndex != index) {
		int oldIndex = index;
		int oldNode = heap[index];
		int oldMinIndex = minIndex;
		int oldMinNode = heap[minIndex];
		
		// update the current index node
		nodeToIndex[oldNode] = oldMinIndex;
		nodeToIndex[oldMinNode] = oldIndex;
		
		heapswap(minIndex, index);
		pushDown(minIndex);
	}
}

void pushUp(int index) {
	while (index > 1 && dist[heap[index / 2]] < dist[heap[index]]) {

		int oldIndex = index;
		int oldNode = heap[index];
		int oldMinIndex = index / 2;
		int oldMinNode = heap[index / 2];

		// update the current index node
		nodeToIndex[oldNode] = oldMinIndex;
		nodeToIndex[oldMinNode] = oldIndex;

		heapswap(index / 2, index);
		index = index / 2;
	}
}

int main() {
	fin >> N >> M;

	for (int i = 1; i <= N; ++i)
		dist[i] = INF;

	for (int i = 1; i <= M; ++i) {
		int A, B, C;
		fin >> A >> B >> C;
		G[A].push_back(make_pair(B, C));
	}

	dist[1] = 0;
	heap[++heapSize] = 1;
	nodeToIndex[1] = 1;

	while (heapSize > 0) {
		int node = heap[1];   
		heapswap(1, heapSize);
		--heapSize;
		if (heapSize > 0)
			pushDown(1);

		for (size_t neighIndex = 0; neighIndex < G[node].size(); ++neighIndex) {
			int neigh = G[node][neighIndex].first;
			int cost = G[node][neighIndex].second;

			if (dist[node] + cost < dist[neigh]) {
				dist[neigh] = dist[node] + cost;

				if (nodeToIndex[neigh] == 0) {
					heap[++heapSize] = neigh;
					nodeToIndex[neigh] = heapSize;
				}

				pushUp(nodeToIndex[neigh]);
			}
		}
	}

	for (int i = 2; i <= N; ++i) {
		fout << (dist[i] == INF ? 0 : dist[i]) << ' ';
	}

	return 0;
}