#include <fstream>
#include <vector>
#include <queue>

struct edge {
	int con;
	int len;
};

struct node {
	int dist;
	std::vector <edge> edges;
};

node graph[50000];

struct nodedist {
	int node;
	int dist;
};

bool operator< (nodedist const& val1, nodedist const& val2) {
	return val1.dist > val2.dist;
}

std::priority_queue <nodedist> prq;

int main() {
	std::ifstream fin("dijkstra.in");
	std::ofstream fout("dijkstra.out");
	int nrn, nrm, pos1, pos2, len;
	nodedist sav;
	fin >> nrn >> nrm;
	for (int index = 0; index < nrn; index++) {
		graph[index] = { -1, {} };
	}
	for (int index = 0; index < nrm; index++) {
		fin >> pos1 >> pos2 >> len;
		pos1--;
		pos2--;
		graph[pos1].edges.push_back({ pos2, len });
		graph[pos2].edges.push_back({ pos1, len });
	}
	prq.push({ 0, 0 });
	while (!prq.empty()) {
		sav = prq.top();
		prq.pop();
		if (graph[sav.node].dist == -1) {
			graph[sav.node].dist = sav.dist;
			for (int index = 0; index < graph[sav.node].edges.size(); index++) {
				if (graph[graph[sav.node].edges[index].con].dist == -1) {
					prq.push({ graph[sav.node].edges[index].con, sav.dist + graph[sav.node].edges[index].len });
				}
			}
		}
	}
	for (int index = 1; index < nrn; index++) {
		fout << graph[index].dist << " ";
	}
}