#include <iostream>
#include <vector>
#define MAX 50010
#define INFINITY 1 << 30

using namespace std;

typedef struct nod {
	int dest;
	int cost;
} nod;

int heapNr = 0;
// vec[i] == distanta de la nodul 0 la nodul i
// heap[i] - indexul in cadrul lui vec - ordonare dupa vec[i]
// pos[i] - pozitia in cadrul heapului a indexului
int vec[MAX], heap[MAX], pos[MAX];
bool visited[MAX];

void upheap(int heapPosition) {

	int me = heapPosition;
	int dad = (me - 1) >> 1;

	while (me != 0) {
		if (vec[heap[me]] < vec[heap[dad]]) {
			pos[heap[me]] = dad;
			pos[heap[dad]] = me;

			int aux = heap[me];
			heap[me] = heap[dad];
			heap[dad] = aux;

			me = dad;
			dad = (me - 1) >> 1;
		}
		else {
			break;
		}
	}
}

void downHeap(int heapPosition) {

	int child1 = (heapPosition << 1) + 1;
	int child2 = (heapPosition << 1) + 2;

	while (true) {
		// daca nu exista niciun copil break;
		if (child1 >= heapNr) {
			break;
		}

		// daca exista doar un copil
		else if (child2 == heapNr) {
			if (vec[heap[heapPosition]] < vec[heap[child1]]) {
				break;
			}
			else {
				pos[heap[child1]] = heapPosition;
				pos[heap[heapPosition]] = child1;

				int aux = heap[child1];
				heap[child1] = heap[heapPosition];
				heap[heapPosition] = aux;

				heapPosition = child1;
				child1 = (heapPosition << 1) + 1;
				child2 = (heapPosition << 1) + 2;
			}
		}

		// daca exista ambii copii
		else if (child2 < heapNr) {
			if (vec[heap[child1]] < vec[heap[child2]]) {
				if (vec[heap[heapPosition]] < vec[heap[child1]]) {
					break;
				}
				else {
					pos[heap[child1]] = heapPosition;
					pos[heap[heapPosition]] = child1;

					int aux = heap[child1];
					heap[child1] = heap[heapPosition];
					heap[heapPosition] = aux;

					heapPosition = child1;
					child1 = (heapPosition << 1) + 1;
					child2 = (heapPosition << 1) + 2;
				}
			}
			else {
				if (vec[heap[heapPosition]] < vec[heap[child2]]) {
					break;
				}
				else {
					pos[heap[child2]] = heapPosition;
					pos[heap[heapPosition]] = child2;

					int aux = heap[child2];
					heap[child2] = heap[heapPosition];
					heap[heapPosition] = aux;

					heapPosition = child2;
					child1 = (heapPosition << 1) + 1;
					child2 = (heapPosition << 1) + 2;
				}
			}
		}
	}
}

// vec[vecIndex] s-a modificat deci trebuie sa modific pozitia lui vecIndex in heap
void changePriority(int vecIndex) {
	int dad = (pos[vecIndex] - 1) >> 1;
	if (pos[vecIndex] != 0 && vec[heap[pos[vecIndex]]] < vec[heap[dad]]) {
		upheap(pos[vecIndex]);
	}
	// refacere heap in jos de la pozitia vecIndex
	else {
		downHeap(pos[vecIndex]);
	}
}

void addToHeap(int vecIndex) {
	if (visited[vecIndex])
		return;

	// nu exista in heap
	if (pos[vecIndex] == -1) {
		int heapPosition = heapNr;
		heap[heapPosition] = vecIndex;
		pos[vecIndex] = heapPosition;

		upheap(heapPosition);
		heapNr++;
	}
	// exista in heap
	else {
		changePriority(vecIndex);
	}	
}



void deleteFromHeap(int vecIndex) {
	// interschimb pozitiile pos[vecIndex], pos[heap[heapPosition]]
	// pozitia de la timpul time e interschimbata cu pozitia ultimei valori din heap
	int heapPosition = heapNr - 1;
	pos[heap[heapPosition]] = pos[vecIndex];

	// interschimb heap[pos[vecIndex]] u heap[heapPosition]
	// interschimb valoarea care trebuie stearsa cu ultima valoare din heap
	int aux = heap[pos[vecIndex]];
	heap[pos[vecIndex]] = heap[heapPosition];
	heap[heapPosition] = aux;

	heapNr--;

	// refacere heap in sus de la pozitia time
	int dad = (pos[vecIndex] - 1) >> 1;
	if (pos[vecIndex] != 0 && vec[heap[pos[vecIndex]]] < vec[heap[dad]]) {
		upheap(pos[vecIndex]);
	}

	// refacere heap in jos de la pozitia time
	else {
		downHeap(pos[vecIndex]);
	}
	pos[vecIndex] = -1;
}

void popMin() {
	if (heapNr > 0)
		deleteFromHeap(heap[0]);
}

int getMin() {
	return vec[heap[0]];
}

int main() {

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

	int n, m;
	scanf("%i%i", &n, &m);
	vector<nod*>* vecini = new vector<nod*>[n];
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%i%i%i", &a, &b, &c);
		a--;
		b--;
		nod* n = new nod();
		n->dest = b;
		n->cost = c;
		vecini[a].push_back(n);
	}

	for (int i = 0; i < n; i++) {
		vec[i] = INFINITY;
		visited[i] = false;
		pos[i] = -1;
	}
	vec[0] = 0;
	visited[0] = true;
	pos[0] = -2;
	for (int i = 0; i < vecini[0].size(); i++) {
		vec[vecini[0][i]->dest] =  vecini[0][i]->cost;
		addToHeap(vecini[0][i]->dest);
	}
	
	while(heapNr > 0 && vec[heap[0]] != INFINITY) {
		int min = getMin();
		popMin();
		visited[min] = true;
		
		for (int i = 0; i < vecini[min].size(); i++) {
			nod* vecin = vecini[min][i];
			if (!visited[vecin->dest]) {
				// daca calea de la sursa la vecin e mai scurta prin min relaxez drumul
				if (vec[vecin->dest] > vec[min] + vecin->cost) {
					vec[vecin->dest] = vec[min] + vecin->cost;
					addToHeap(vecin->dest);
				}
			}
		}
	}

	for (int i = 1; i < n; i++) {
		if (vec[i] == INFINITY)
			printf("0 ");
		else 
			printf("%i ", vec[i]);
	}

	fclose(stdin);
	fclose(stdout);

	//system("pause");
	return 0;
}