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

typedef struct nodSiCost {
	int nod, cost;
} nodSiCost;

const int numarMare = 0x8fffffff;
bool vizitat[50001];
int rezultat[50001];
std::vector< std::pair<int, int> > graf[50001];
std::set< std::pair<int, int> > dijkstra;

int main() {
	int n, m;

	FILE *fin = fopen("dijkstra.in", "r");
	fscanf(fin, "%d%d", &n, &m);
	for(int i=1; i<=m; i++) {
		int de_la, pana_la, cost;
		fscanf(fin, "%d%d%d", &de_la, &pana_la, &cost);
		graf[de_la].push_back(std::make_pair(cost, pana_la));
	}
	fclose(fin);

	/* 90puncte - 100puncte */
	for(int i=2; i<=n; i++)
		rezultat[i] = numarMare;
	/* --- */

	dijkstra.insert(std::make_pair(0, 1));
	while(!dijkstra.empty()) {
		std::set< std::pair<int, int> >::iterator undeSunt;
		undeSunt = dijkstra.begin();

		int nod = undeSunt->second, costPanaAici = undeSunt->first;
		//printf("Sunt la nodul %d si costul e %d\n", nod, costPanaAici);
		dijkstra.erase(undeSunt);

		rezultat[nod] = costPanaAici;
		
		for(unsigned long i=0; i<graf[nod].size(); i++) {
			int urm = graf[nod][i].second;
			int nextcost = costPanaAici + graf[nod][i].first;
			//printf("Pot sa ma duc in nodul %d si costul ar fi %d\n", urm, nextcost);

			/* 90puncte - 100puncte */
			if(nextcost < rezultat[urm]) {
				if(rezultat[urm] == numarMare) {
					/* e normal, doar dau update */
				} else {
					/* avem deja alte drumuri care duc aici pe care trebuie sa le stergem ca sa nu mai trecem pe la ele (SLOW) */
					dijkstra.erase(dijkstra.find(std::make_pair(rezultat[urm], urm)));
				}

				rezultat[urm] = nextcost;
				dijkstra.insert(std::make_pair(nextcost, urm));
			}
			/* --- */

		}

	}

	FILE *fout = fopen("dijkstra.out", "w");
	for(int i=2; i<=n; i++)
		fprintf(fout, "%d ", rezultat[i]);
	fclose(fout);

	return 0;
}