public static class Info implements Comparable<Info>{

int node1;

int node2;

int cost;

Info (int node1, int node2, int cost) {

this.node1 = node1;

this.node2 = node2;

this.cost = cost;

}

public int compareTo(Info other) {

return Integer.compare(this.cost, other.cost);

}

}

static Queue<Info> pQue; // 노드와 연결된 가중치가 작은 정보부터 poll되는 우선 순위 큐

static Set<Integer> set; // 그래프에 포함된 노드 정보

static List<List<Info>> graph; // 노드와 (노드, 연결 노드, 가중치)를 저장한 ArrayList

static int startNode; // 시작 노드

static int answer; // 최소 비용

int solution(int n, int[][] costs) {

graph = new ArrayList<>();

for(int i = 0; i < n; i++) {

graph.add(new ArrayList<>());

}

// 1

for (int[] cost : costs) {

int node1 = cost[0];

int node2 = cost[1];

int edge = cost[2];

graph.get(node1).add(new Info(node1, node2, edge));

graph.get(node2).add(new Info(node1, node2, edge));

}

startNode = costs[0][0];

// 2

return prim(n);

}

int prim(int n) {

answer = 0;

// 2-1

pQue = new PriorityQueue<>();

set = new HashSet<>();

pQue.addAll(graph.get(startNode));

set.add(startNode);

while(set.size() < n) {

// 2-2

Info info = pQue.poll();

if (set.contains(info.node1) && set.contains(info.node2)) continue;

// 2-3

int newNode = set.contains(info.node1) ? info.node2 : info.node1;

answer += info.cost;

set.add(newNode);

// 2-4

for (Info next : graph.get(newNode)) {

if (!set.contains(next)) {

pQue.add(next);

}

}

}

return answer;

}

public static void main(String[] args) {

Solution42861 s = new Solution42861();

System.out.println(s.solution(4, new int[][] {

{0, 1, 1}, {0, 2, 2}, {1, 2, 5}, {1, 3, 1},{2, 3, 8}

}));

}

}