#include <iostream>
#include <vector>
#include <utility> // pair
#include <queue> // pq
#define MAX 100 // n: 노드의 수
#define INF 99999999
using namespace std;

vector< pair<int, int> > graph[MAX]; // graph[from] = ((to, weight), (to, weight), ...)
vector<int> dist(MAX, INF); // 처음에는 모두 INF로 초기화

void update(int from, int old, priority_queue< pair<int, int>> * pq) {
	int edge = graph[from].size(); // number of adjacent nodes
	int i;

	for (i = 0; i < edge; i++) {
		int to = graph[from][i].first;
		int weight = graph[from][i].second;
		int newDist = old + weight; // newly updated dist

		// 더 짧은 경로를 발견하면 dist를 update하고 pq에 집어넣음
		if (newDist < dist[to]) {
			dist[to] = newDist;
			pq->push(make_pair(-newDist, to));
		}
	}
}

void dijkstra(int src) {
	// init	
	dist[src] = 0;
	priority_queue< pair<int, int> > pq; // (weight, from)

	pq.push(make_pair(0, src));
	while (!pq.empty()) {
		int weight = -pq.top().first;
		int from = pq.top().second;
		pq.pop();

		if (dist[from] < weight) continue; // 기존의 경로가 지금 꺼낸 것보다 더 짧다면 지금 꺼낸 것을 무시
		else update(from, weight, &pq);
	}
}

int main() {
	int N;
	int i, from, to, weight;
	cin >> N;

	for (i = 0; i < N; i++) {
		cin >> from >> to >> weight;
		graph[from].push_back(make_pair(to, weight));
		graph[to].push_back(make_pair(from, weight));
	}

	dijkstra(0);

	for (i = 0; i < N; i++) cout << "dist[" << i << "]: " << dist[i] << endl;

	return 0;
}

#include <iostream>
#include <vector>
#include <utility> // pair
#include <queue> // pq
#define MAX 100 // max number of nodes
#define INF 99999999
using namespace std;

vector< pair<int, int> > graph[MAX]; // graph[from] = ((to, weight), (to, weight), ...)
vector<int> dist(MAX, INF); // init to INF at first
bool check[MAX];

void update(int from, priority_queue< pair<int, int> > * pq) {
	int edge = graph[from].size(); // number of adjacent nodes
	int i;

	for (i = 0; i < edge; i++) {
		int to = graph[from][i].first;
		int weight = graph[from][i].second;

		if (!check[to]) {
			if (weight < dist[to]) dist[to] = weight;
			pq->push(make_pair(-weight, to));
		}
	}
}

void prim(int start) {
	// init
	dist[start] = 0;
	priority_queue< pair<int, int> > pq; // (weight, from)

	pq.push(make_pair(0, start));
	while (!pq.empty()) {
		int weight = -pq.top().first;
		int to = pq.top().second;
		pq.pop();

		if (!check[to]) {
			update(to, &pq);
			check[to] = true;
		}
	}
}

int main() {
	int N, E; // node, edge
	int i, from, to, weight;
	cin >> N >> E;

	for (i = 0; i < E; i++) {
		cin >> from >> to >> weight;
		graph[from].push_back(make_pair(to, weight));
		graph[to].push_back(make_pair(from, weight));
	}

	prim(1);

	for (i = 1; i <= N; i++) cout << "dist[" << i << "]: " << dist[i] << endl;

	return 0;
}