MBST solution
IntuitionThe problem requires us to construct a graph such that:
Node 0 is reachable from all other nodes.
Each node has at most threshold outgoing edges.
The m
# Intuition
The problem requires us to construct a graph such that:
1. Node 0 is reachable from all other nodes.
2. Each node has at most `threshold` outgoing edges.
3. The maximum edge weight in the resulting graph is minimized.

This boils down to:
- Reducing the graph to satisfy the outgoing edge constraint per node.
- Using a priority-based search (e.g., Dijkstra's algorithm) to find the optimal configuration of edges that minimizes the maximum edge weight.

The idea is to use a modified shortest path algorithm to explore all possible configurations while respecting the conditions.

# Approach
1. **Graph Construction**:
   - Parse the input edges into an adjacency list for easier traversal.

2. **Priority Queue**:
   - Use a priority queue (min-heap) to keep track of nodes and the current maximum edge weight. The priority queue ensures that we process paths with smaller weights first.

3. **Relaxation and Edge Constraint**:
   - While traversing, maintain the `dis` array to track the smallest maximum weight to reach each node.
   - For each node, enforce the threshold constraint by ensuring the number of outgoing edges considered does not exceed `threshold`. This can be done by sorting or selectively picking the smallest weights.

4. **Early Exit**:
   - If all nodes are reachable with the given constraints, return the minimized maximum edge weight. Otherwise, return `-1`.

5. **Edge Validation**:
   - After constructing the path, verify that all conditions are met (e.g., `threshold` outgoing edges, connectivity).

# Complexity
- **Time Complexity**:
  - Constructing the adjacency list: $$O(E)$$, where \(E\) is the number of edges.
  - Dijkstra's traversal with \(n\) nodes and up to \(E\) edges: $$O((E + n) \log n)$$.
  - Enforcing the outgoing edge threshold: $$O(n \cdot \log n)$$ for sorting edges.
  - Total: $$O(E \log n + n \log n)$$.

- **Space Complexity**:
  - Adjacency list: $$O(E)$$.
  - Priority queue and distance array: $$O(n)$$.
  - Total: $$O(E + n)$$.


# Code
```java []
class Solution {
    public int minMaxWeight(int n, int[][] edges, int threshold) {
        Map<Integer, List<int[]>> map = new HashMap<>();
        for (int[] edge :  edges) {
            List<int[]> list = map.getOrDefault(edge[1], new ArrayList<>());
            list.add(edge);
            map.put(edge[1], list);
        }


        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE);
        PriorityQueue<int[]> queue = new PriorityQueue<>((int[] x, int[] y) -> {
            return x[2] < y[2] ? -1 : 1;
        });
        int result = -1;
        queue.add(new int[]{0,0,0});
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            if (node[1] < dis[node[0]]) {
                result = Math.max(result, node[2]);
                dis[node[0]] = node[2];
                for (int[] next : map.getOrDefault(node[0], new ArrayList<>())) {
                    int to = next[0];
                    if (dis[node[0]] + next[2] < dis[to]) {
                        queue.add(new int[]{to, dis[node[0]] + next[2], next[2]});

                    }
                }
            }
        }
        for (int d : dis) if (d == Integer.MAX_VALUE) return -1;
        return result;
    }
}
```
['Java']