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

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

struct cmp_costMaiMic {
	bool operator() (nodSiCost a, nodSiCost b) {
		return a.cost < b.cost;
	}
};

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 a, b, c;
		fscanf(fin, "%d%d%d", &a, &b, &c);
		graf[a].push_back(std::make_pair(c, b));
	}
	fclose(fin);

	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);
		if(vizitat[nod]) {
			//printf("Dar deja am mai fost pe aici\n");
			continue;
		}

		vizitat[nod] = true;
		rezultat[nod] = costPanaAici;
		
		for(unsigned long i=0; i<graf[nod].size(); i++) {
			int urm = graf[nod][i].second;
			if(vizitat[urm]) continue;
			int nextcost = costPanaAici + graf[nod][i].first;
			//printf("Pot sa ma duc in nodul %d si costul ar fi %d\n", 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;
}