There are `n`

cities labeled from `1`

to `n`

. You are given the integer `n`

and an array `connections`

where `connections[i] = [xi, yi, costi]`

indicates that the cost of connecting city `xi`

and city `yi`

(bidirectional connection) is `costi`

.

Return *the minimum cost to connect all the *

`n`

`n`

cities, return `-1`

,The **cost** is the sum of the connections' costs used.

**Example 1:**

Input:n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]Output:6Explanation:Choosing any 2 edges will connect all cities so we choose the minimum 2.

**Example 2:**

Input:n = 4, connections = [[1,2,3],[3,4,4]]Output:-1Explanation:There is no way to connect all cities even if all edges are used.

**Constraints:**

`1 <= n <= 10^4`

`1 <= connections.length <= 10^4`

`connections[i].length == 3`

`1 <= xi, yi <= n`

`xi != yi`

`0 <= costi <= 10^5`

`The description was taken from `

https://leetcode.com/problems/connecting-cities-with-minimum-cost/.

`#O(E(Log(V))) Time, O(E+V) Space`

**class** **Solution**:

**def** **minimumCost**(self, n: int, connections: List[List[int]]) -> int:

adjacency, seen = {}, {}

output = **0**

**for** node **in** range(**1**, n+**1**):

adjacency[node] = []

**for** source, dest, cost **in** connections:

adjacency[source].append((cost, dest))

adjacency[dest].append((cost, source))

heap = [(**0**,**1**)]

**while** heap:

cost, node = heapq.heappop(heap)

**if** node **in** seen:

**continue**

seen[node] = True

output += cost

**for** path_cost, neighbor **in** adjacency[node]:

**if** neighbor **not** **in** seen:

heapq.heappush(heap, (path_cost, neighbor))

**if** len(seen) < n:

**return** -**1**

**return** output

This problem is very similar to *Minimum Cost to Connect all Points*. We are given an undirected weighted graph and are asked for the minimum cost to connect all of the points.

This type of problem belongs in the category of *Minimum Spanning Trees*.

There are many ways to solve these, but maybe one of the more intuitive solutions is Prim's algorithm, a variation of Dijkstra's which we can use to find the minimum cost to connect the shortest paths of each node by traversing each shortest path.

Let's start by initializing our adjacency list which we will use to map each node to its neighbors, and our dictionary for nodes that we have seen.

` adjacency, seen = {}, {}`

We will also need a counter that we'll output which we will increment by the weights of the shortest paths we travel.

` output = `

**0**

Let's go ahead and step through the list of nodes and initialize an empty list for each node that we will fill with its neighbors in a moment.

` `

**for** node **in** range(**1**, n+**1**):

adjacency[node] = []

For each connection from a node to its neighbor, we'll push the cost and the neighbor into the node's adjacency list. We will also need to do the same for the neighbor's list since these are undirected edges.

` `

**for** source, dest, cost **in** connections:

adjacency[source].append((cost, dest))

adjacency[dest].append((cost, source))

Next, we will begin our shortest path traversal starting from the first node.

We will initialize a heap with a tuple of zero and one. Since we are choosing node one as the source node, it will have an initial cost of zero to travel to it.

` heap = [(`

**0**,**1**)]

While we have nodes in the heap, we will continue traveling the shortest paths.

` `

**while** heap:

Each iteration will begin by popping the current shortest path between any two nodes from the heap and if we have seen the destination node before, we will skip it so that we don't revisit it.

If we have already seen it before, that means we have also seen a shorter path to it already.

` cost, node = heapq.heappop(heap)`

**if** node **in** seen:

**continue**

If not, we will mark it as seen, increment the output by the cost to get to it so that we are essentially traveling the path, and if we have not seen its neighbors, we will push them into the heap next with the cost to travel the path to them.

` seen[node] = True`

output += cost

**for** path_cost, neighbor **in** adjacency[node]:

**if** neighbor **not** **in** seen:

heapq.heappush(heap, (path_cost, neighbor))

If the length of nodes we have seen is less than the number of nodes we have, then that means there wasn't a path to some of the nodes so we will return a negative one.

Otherwise, we will return the cost to travel each shortest path.

` `

**if** len(seen) < n:

**return** -**1**

**return** output