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

using namespace std;

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

#define INF 1<<31 - 1

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)
			if (distances[heap[leftSon]] <= distances[heap[rightSon]])
				chosenSon = leftSon;
			else
				chosenSon = rightSon;
		else
			if(leftSon)
                chosenSon = leftSon;
            else
                return;
        if (distances[heap[chosenSon]] >= distances[heap[node]])
            return;

		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(heapSize);
}


void update(int i) {
	if (poz[i] > 1 && distances[i] < distances[heap[poz[i]/2]])
		percolate(poz[i]);
	else
		sift(poz[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;
		poz[i] = -1;
	}
	distances[1] = 0;
	push(1);

	while (heapSize) {
		a = pop();

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

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

	return 0;
}