#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>

constexpr auto INF = 0x3f3f3f3f;

using namespace std;

class graph {
	int nodes;
	vector<vector<pair<int, int>>> list;
public:
	graph(int);
	graph(string);

	void addEdge(int, int, int);

	void dijkstra(int);
};

graph::graph(int v) {
	this->nodes = v;
	list.resize(v+1);
}

graph::graph(string file) {
	ifstream f(file);

	f >> nodes;
	list.resize(nodes+1);

	int m;
	f >> m;

	for (int i = 0; i < m; i++) {
		int x, y, c;
		f >> x >> y >> c;
		addEdge(x, y, c);
	}

	f.close();
}

void graph::addEdge(int x, int y, int c=0) {
	list[x].push_back(make_pair(y, c));
	list[y].push_back(make_pair(x, c));
}

void graph::dijkstra(int src) {
	vector<int> dist(nodes+1, INF);

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

	pq.push(make_pair(0, src));
	dist[src] = 0;

	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();

		for (auto it : list[u]) {
			int w = it.second;
			int v = it.first;

			if (dist[v] > dist[u] + w)
			{
				dist[v] = dist[u] + w;
				pq.push(make_pair(dist[v], v));
			}
		}
	}
	
	ofstream g("bfs.out");
	for (int i = 2; i <= nodes; i++) {
		g << dist[i] << " ";
	}
	g.close();
}

int main() {
	graph G("bfs.in");
	G.dijkstra(1);
}