package hackerrank;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

/**
 * https://www.hackerrank.com/challenges/primsmstsub
 */
public class PrimsSpecialSubtree {
    private static int mst(Map<Integer, List<Edge>> adjList, int start) {
        // TODO
        return 0;
    }

    private static class Edge {
        private final int v1;
        private final int v2;
        private final int weight;

        public Edge(int v1, int v2, int weight) {
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
        }

        public int either(int v) {
            return v1;
        }

        public int other(int v) {
            if (v == v1) {
                return v2;
            }
            return v1;
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        Map<Integer, List<Edge>> adjList = new HashMap<>();
        for (int vertex = 0; vertex < n; vertex++) {
            adjList.put(vertex, new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            int r = in.nextInt();
            adjList.get(x).add(new Edge(x, y, r));
            adjList.get(y).add(new Edge(x, y, r));
        }
        int s = in.nextInt();
        System.out.println(mst(adjList, s));
    }
}

@@ -89,34 +89,92 @@
 til.
-List;%0Aimport java.util.Map
+HashSet;%0Aimport java.util.List;%0Aimport java.util.Map;%0Aimport java.util.PriorityQueue
 ;%0Aim
@@ -196,16 +196,38 @@
 Scanner;
+%0Aimport java.util.Set;
 %0A%0A/**%0A *
@@ -386,49 +386,1201 @@
 nt s
-tart) %7B%0A        // TODO%0A        return 0;
+ource) %7B%0A        PriorityQueue%3CEdge%3E queue = new PriorityQueue%3C%3E();%0A        Set%3CInteger%3E marked = new HashSet%3C%3E();%0A        List%3CEdge%3E mst = new ArrayList%3C%3E();%0A        visit(adjList, source, marked, queue);%0A        while (!queue.isEmpty()) %7B%0A            Edge edge = queue.remove();%0A            int v1 = edge.either();%0A            int v2 = edge.other(v1);%0A            if (marked.contains(v1) && marked.contains(v2)) %7B%0A                continue;%0A            %7D%0A            mst.add(edge);%0A            if (!marked.contains(v1)) %7B%0A                visit(adjList, v1, marked, queue);%0A            %7D%0A            if (!marked.contains(v2)) %7B%0A                visit(adjList, v2, marked, queue);%0A            %7D%0A        %7D%0A        int totalWeight = 0;%0A        for (Edge edge : mst) %7B%0A            totalWeight += edge.weight;%0A        %7D%0A        return totalWeight;%0A    %7D%0A%0A    private static void visit(Map%3CInteger, List%3CEdge%3E%3E adjList, int source,%0A                              Set%3CInteger%3E marked, PriorityQueue%3CEdge%3E queue) %7B%0A        marked.add(source);%0A        for (Edge edge : adjList.get(source)) %7B%0A            if (!marked.contains(edge.other(source))) %7B%0A                queue.add(edge);%0A            %7D%0A        %7D
 %0A   
@@ -1612,16 +1612,44 @@
 ass Edge
+ implements Comparable%3CEdge%3E
  %7B%0A     
@@ -1907,29 +1907,24 @@
  int either(
-int v
 ) %7B%0A        
@@ -2075,32 +2075,154 @@
 rn v1;%0A        %7D
+%0A%0A        @Override%0A        public int compareTo(Edge o) %7B%0A            return Integer.compare(weight, o.weight);%0A        %7D
 %0A    %7D%0A%0A    publ
@@ -2449,17 +2449,17 @@
 ertex = 
-0
+1
 ; vertex
@@ -2460,16 +2460,17 @@
 vertex %3C
+=
  n; vert

Solve Prim's; Special Subtree