class MSTKruskal {
    static int V, E;             // 정점, 간선 개수
    static Edge[] edgeList;      // 간선 리스트
    static int[] parents;        // 서로소 집합을 위한 parents 배열

    // 간선을 표현할 클래스
    static class Edge implements Comparable<Edge> {
        int from, to, weight;      // 출발 노드, 도착 노드, 가중치

        public Edge(int from, int to, int weight) {
            super();
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        // 가중치 기준 오름차순 정렬
        @Override
        public int CompareTo(Edge e) {
            return Integer.compare(this.weight, e.weight);     // 음수 가중치 언더플로우 주의
        }
    }

    // union-find의 make-set
    private static void makeSet() {
        parents = new int[V];
        for (int i=0; i<V; i++) parents[i] = i;
    }

    // union-find의 find-set
    private static int findSet(int a) {
        if (parnets[a] == a) return a;
        return parents[a] = findSet(parents[a]);
    }

    // union-find의 union
    private static boolean union(int a, int b) {
        int aRoot = findSet(a);
        int bRoot = findSet(b);

        if (aRoot == bRoot) return false;

        parents[bRoot] = aRoot;
        return true;
    }

    public static void main(String[] args) {
        edgeList = new Edge[E];
        for (int i=0; i<E; i++) edgeList[i] = new Edge(from, to, weight);   // 간선정보를 간선 리스트에 저장

        Arrays.sort(edgeList);       // 그리디하게 최소 비용 간선을 먼저 선택할 것이므로 오름차순 정렬

        makeSet();                   // 모든 간선을 하나씩 선택해보기위해 각 노드를 서로소 집합으로 표현

        int accumEdge = 0;                         // 선택된 누적 간선 수
        int totalWeight = 0;                       // 총 가중치
        for (Edge edge : edgeList) {               // 가중치가 작은 간선부터 선택하며
            if (union(edge.from, edge.to)) {       // 두 정점간 사이클이 존재하지 않는다면
                totalWeight += edge.weight;        // 해당 간선을 선택
                if (++accumEdge >= V-1) break;      // 모든 정점이 연결되면 종료
            }
        }
    }

}

class MSTPrim {
    public static void main(String[] args) { 
        int N;                                  // 정점 개수
        int[][] adjLMatrix = new int[N][N];     // 모든 인접 정점 간 가중치 정보 저장
        boolean visited = new boolean[N];       // 정점 방문 여부
        int[] minEdge = new int[N];             // 각 노드 별 간선 가중치 최솟값 저장

        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) adjMatrix[i][j] = w;     // 인접 정점 간 가중치 저장
            minEdge[i] = Integer.MAX_VALUE;                  // 최솟값을 위해 최댓값으로 초기화
        }

        int totalWeight = 0;          // 최종 최소 신장 트리 비용
        minEdge[0] = 0;               // 0번 인덱스 노드부터 시작 설정(임의의 노드)

        for (int i=0; i<N; i++) {
            // 1) 신장트리에 포함되지 않은 정점 중 최소 간선 비용의 정점을 찾기
            int minWeight = Integer.MAX_VALUE;                 // 최소 간선 비용
            int minVertex = -1;                                // 최소 간선 비용 노드

            for (int j=0; j<N; j++) {
                if (!visited[j] && minEdge[j]<minWeight) {     // 방문하지 않았고, 최소 간선 비용이면 저장
                    minWeight = minEdge[j];
                    minVertex = j;
                }
            }

            visited[minVertex] = true;                         // 해당 정점 최소 비용 신장 트리에 추가하고
            totalWeight += minWeight;                          // 최종 최소 간선 비용 합산

            // 2) 선택된 정점 기준으로 신장 트리에 연결되지 않은 타 정점과의 간선 비용을 최솟값으로 업데이트
            for (int j=0; j<N; j++) {
                if (!visited && adjMatrix[minVertex][j] && adjMatrix[minVertex][j]<minEdge[j]) {                                 // 방문하지 않았고, minVertex와 인접하며, minVertex와의 간선 비용이 기존 최소 간선 비용보다 작으면
                    minEdge[j] = adjMatrix[minVertex][j];      // minVertex와의 간선 비용으로 업데이트(최솟값 갱신)
                }
            }

        }
    }
}