1135. Connecting Cities With Minimum Cost

O(ElogE)

```java
class Solution {
    class Step {
        int id;
        int cost;
        Step(int id, int cost) {
            this.id = id;
            this.cost = cost;
        }
    }
    public int minimumCost(int n, int[][] connections) {
        Map<Integer, List<Step>> graph = buildGraph(connections);
        Queue<Step> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);
        pq.offer(new Step(1, 0)); // id start from 1
        Set<Integer> visited = new HashSet<>();

        int result = 0;
        while (!pq.isEmpty()) {
            Step cur = pq.poll();

            if (visited.contains(cur.id)) {
                continue;
            }
            visited.add(cur.id);
            result += cur.cost;

            if (visited.size() == n) {
                return result;
            }
            if (graph.containsKey(cur.id)) {
                for (Step next : graph.get(cur.id)) {
                    pq.offer(next);
                }
            }
        }
        return -1;
    }
    private Map<Integer, List<Step>> buildGraph(int[][] connections) {
        Map<Integer, List<Step>> graph = new HashMap<>();
        for (int[] c : connections) {
            graph.putIfAbsent(c[0], new ArrayList<>());
            graph.get(c[0]).add(new Step(c[1], c[2]));

            graph.putIfAbsent(c[1], new ArrayList<>());
            graph.get(c[1]).add(new Step(c[0], c[2]));
        }
        return graph;
    }
}
```