#include <cstdio>
#include <vector>
#include <utility>

using namespace std;

vector<vector<pair<int, int>>> arcs;
vector<int> distances;

#define INF 1<<30

int heap[50002];
int poz[50002];
int heapSize;



void sift(int node) {
	int leftSon, rightSon, chosenSon, aux;

	while(node < heapSize) {
		leftSon = node * 2 <= heapSize ? node * 2 : 0;
		rightSon = node * 2 + 1 <= heapSize ? node * 2 + 1 : 0;

		if (leftSon && rightSon && distances[heap[leftSon]] < distances[heap[node]] && distances[heap[rightSon]] < distances[heap[node]])
			if (distances[heap[leftSon]] <= distances[heap[rightSon]])
				chosenSon = leftSon;
			else
				chosenSon = rightSon;
		else
			if (rightSon && distances[heap[rightSon]] < distances[heap[node]])
				chosenSon = rightSon;
			else
				if (leftSon && distances[heap[leftSon]]  < distances[heap[node]])
					chosenSon = leftSon;
				else
					break;

		aux = heap[chosenSon];
		heap[chosenSon] = heap[node];
		heap[node] = aux;

		poz[heap[chosenSon]] = chosenSon;
		poz[heap[node]] = node;

		node = chosenSon;
	}
}


void percolate(int node) {
	int aux;
	while (node > 1) {
		if (distances[heap[node / 2]] > distances[heap[node]]) {
			aux = heap[node / 2];
			heap[node/2] = heap[node];
			heap[node] = aux;

			poz[heap[node / 2]] = node / 2;
			poz[heap[node]] = node;

			node /= 2;

		} else
			break;
	}
}


void push(int i) {
	++heapSize;

	poz[i] = heapSize;
	heap[heapSize] = i;

	percolate(i);
}


void update(int i) {
	if (poz[i] > 1 && distances[i] < distances[heap[poz[i]/2]])
		percolate(i);
	else
		sift(i);
}


int pop() {
	int res = heap[1];
	poz[res] = -1;

	heap[1] = heap[heapSize];
	poz[heap[1]] = 1;
	--heapSize;

	sift(1);
	return res;
}


int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	int n, m, a, b, c;

	scanf("%d%d", &n, &m);
	arcs.resize(n+1);
	distances.resize(n+1);

	for(int i=0; i<m; ++i) {
		scanf("%d%d%d", &a, &b, &c);
		arcs[a].push_back(pair<int, int>(b, c));
	}

	for(int i=0; i<=n; ++i)
		distances[i] = INF;
	distances[1] = 0;
	for(int i=1; i<=n; ++i)
		push(i);

	while (heapSize) {
		a = pop();

		for(int i=0; i<arcs[a].size(); ++i)
			if (poz[arcs[a][i].first] != -1)
			{
				b = distances[a] + arcs[a][i].second;
				if (b < distances[arcs[a][i].first]) {
					distances[arcs[a][i].first] = b;
					update(arcs[a][i].first);
				}
			}
	}

	for(int i=2; i<=n; ++i)
        if (distances[i] == INF)
            printf("0 ");
        else
            printf("%d ", distances[i]);

	return 0;
}