Prim's with extra words (Python, beats binary search)
IntuitionThis problem is just asking you to do prim's/dijkstra's algorithm but with extra words like some bs about "thresholds" to make it confusing. It's direc
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
This problem is just asking you to do prim's/dijkstra's algorithm but with extra words like some bs about "thresholds" to make it confusing. It's directed, so you'll need a slight modification to keep track of which edges to actually consider.

# Approach
<!-- Describe your approach to solving the problem. -->
Make an MST starting from node 0. Ignore edges outgoing from 0, and only consider new edges directing towards your MST.
Threshold doesn't matter, you only need to pick the one outgoing edge per node anyway in Prim's.
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(elog(e))
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(e)
# Code
```python3 []
class Solution:
    def minMaxWeight(self, n: int, edges: List[List[int]], threshold: int) -> int:
        #prims - just keep adding the lowest edge that connects something new to 0 (or to something already connected to 0)
        #basically - just pick the best outgoing edge for every node
        incoming = [[] for _ in range(n)]
        for start, end, w in edges:
            incoming[end].append((start, w))
        heap = [(0, 0)]
        added = set()
        ans = 0
        while len(heap) > 0:
            weight, node = heap[0]
            heapq.heappop(heap)
            if node not in added:
                added.add(node)
                ans = max(ans, weight)
                for nNode, nWeight in incoming[node]:
                    if nNode not in added:
                        heapq.heappush(heap, (nWeight, nNode))
        if len(added) == n:
            return ans
        return -1
```
['Python3']