// 위의 그림과 같은 그래프가 주어진다고 가정한다.

// 입력 정보 (그래프의 정보)
// 정점의 개수
const n = 5;
// 간선 정보 [정점, 정점, 가중치]
const edges = [
	[0, 1, 14],
	[0, 2, 12],
	[0, 3, 45],
	[1, 2, 28],
	[1, 3, 9],
	[1, 4, 63],
	[2, 3, 32],
	[3, 4, 51],
];

// 현재 신장 트리에서 인접하지 않은 정점을 표현하기 위한 무한대 값
const INF = Number.MAX_SAFE_INTEGER;

// 간선 정보를 담기 위한 클래스 {정점, 가중치}
class Edge {
	constructor(v, weight) {
		this.v = v; // 맞은편 정점
		this.weight = weight; // 가중치
	}
}

const Prim = (edges, n) => {
	// 결과 MST의 가중치의 합을 알아보자!!
	let sum = 0;

	// 주어진 그래프를 인접 리스트로 만들기 (가중치 정보도 포함해서)
	const graph = Array.from({length: n}, () => []);
	for (let i = 0; i < edges.length; i++) {
		const [from, to, weight] = edges[i];

		graph[from].push(new Edge(to, weight));
		graph[to].push(new Edge(from, weight));
	}

	// 현재까지 알려진 신장 트리의 정점 집합에서 각 정점까지의 거리
	const distance = Array.from({length: n}, () => INF);

	// 현재 신장트리에 추가된 정점 정보
	const selected = Array.from({length: n}, () => false);

	// 1.시작 정점을 넣는다.
	distance[0] = 0;

	// 2. 현재 신장 트리에서 가장 가까운 정점을 추가하고, distance 갱신을 반복한다.
	for (let i = 0; i < n; i++) {
		let u = -1;

		// 현재 신장 트리에 포함되지 않은 정점들 중에서 인접한 정점 중 가장 가까운 정점 찾기
		for (let i = 0; i < n; i++) {
			if (!selected[i] && (u === -1 || distance[u] > distance[i])) {
				u = i;
			}
		}

		// 현재 신장 트리에 포함시킨다.
		selected[u] = true;
		sum += distance[u];

		// 추가한 정점(u)에 인접한 정점들(v)을 다 확인하며 distance를 갱신(더 짧은 거리로)
		for (let i = 0; i < graph[u].length; i++) {
			const {v, weight} = graph[u][i];
			if (!selected[v] && distance[v] > weight) {
				distance[v] = weight;
			}
		}
	}

	return [distance, sum];
};

const [distance, sum] = Prim(edges, n);
console.log(distance, sum); // [0, 14, 12, 9, 51] 86