#include <stdio.h>
#include <vector>
#include <climits>
#include <queue>

long N, M;
long W[50001];

struct node {
    long index;
    long weight;
};

class CompareNodeWeight {
public:
	bool const operator()(node &u, node &v) {
		return (u.weight > v.weight);
	}
};

int main () {
	FILE* input = fopen("dijkstra.in", "r");
	FILE* output = fopen("dijstra.out", "w");

	fscanf(input, "%ld %ld", &N, &M);

	std::vector< std::vector<node> > adjList (N+1, std::vector<node>());

	for (int i = 0; i <= 50001; i++) W[i] = LONG_MAX;

	long u, v, w;
	for (long i = 0; i < M; i++) {
		fscanf(input, "%ld %ld %ld", &u, &v, &w);

		adjList[u].push_back(node());

		long listSize = adjList[u].size();

		adjList[u][listSize - 1].index = v;
		adjList[u][listSize - 1].weight = w;
	}

	//Dijkstra
	W[1] = 0;

	std::priority_queue<node, std::vector<node>, CompareNodeWeight> Q;

	node root;
	root.index = 1;
	root.weight = 0;
	Q.push(root);

	while (!Q.empty()) {
		root = Q.top();
		Q.pop();

		if (root.weight <= W[root.index]) {
			for (unsigned long i = 0; i < adjList[root.index].size(); i++) {
				if (W[adjList[root.index][i].index] > W[root.index] + adjList[root.index][i].weight) {
					W[adjList[root.index][i].index] = W[root.index] + adjList[root.index][i].weight;

					node newNode;
					newNode.index = adjList[root.index][i].index;
					newNode.weight = W[adjList[root.index][i].index];

					Q.push(newNode);
				}
			}
		}
	}

	for (long i = 2; i <= N; i++) {
		printf("%ld ", W[i]);
	}

	fclose(input);
	fclose(output);

	return 0;
}