Reason to reverse graph || How to approach the problem
IntuitionThe question asks us
To check if from all nodes i can reach zero or not.
Each node has at most threshold outgoing edges.
Minimize the maximum edge weig
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The question asks us 
1. To check if from all nodes i can reach zero or not. 
2. Each node has at most threshold outgoing edges.
3. Minimize the maximum edge weight in the resulting graph

Problem wants us to form a new graph and see if we can reach the node zero and we should try to use only light weights.
# Approach
<!-- Describe your approach to solving the problem. -->
**Weight Part**
Lets first focus on weight part only and use pen paper right.
What if I tell you that my answer for this particular graph is ans_w than it means that all edges that i use has weight less than or equal to ans_w. `w_i <= ans_w`.

Why not i try for all values of w `1<=w<=10^6`. And see if w can be my answer or not.

Suppose we have a blackbox where I pass a weight and it returns true if w can be ans_w or not.

**Example**
For w=1   =>   blackbox returns `false`
For w=2   =>   blackbox returns `false`
For w=3   =>   blackbox returns `false`
For w=4   =>   blackbox returns `false`
For w=5   =>   blackbox returns `false`
For w=6   =>   blackbox returns `true`
For w=7   =>   blackbox returns `true`
For w=8   =>   blackbox returns `true`
... for futher weights it will true. 
**But Why?**

If we assume that we can form a graph such that from all nodes i can reach node 0 and maximum weight is 6.
Then for all w > 6 blackbox returns true.
Cause blackbox checks if from all nodes i can reach node 0 and i only use weight less then the weight passed to this blackbox.

So we have something like this. Lets try to see it  on number line

```
    false false false false false  true true true 
     1     2     3     4     5      6    7    8 
``` 
# Binary Search
So here one half returns true and other half returns false. 
That is
1. if for a particular weight `w_i` blackbox returns false then for all the weights less then `w_i` blackbox will return false.
2. if for a particular weight `w_j` blackbox returns true then for all the weights greater then `w_j` blackbox will return true.

So here we can use binary search as for a particular weight we will either move to left or right.


# Reverse graph
If from all nodes i check if i can reach the node 0 then it will be too slow and will end up take quadratic time. We have to solve it in linear time.
Instead of checking if i can reach node 0 from all others node. Why not check if i can reach other nodes from node 0. This will take linear time $$O(V+E)$$.
First invert the graph that is 
we have been given `edges[i] = [Ai, Bi, Wi]` indicates that there is an edge going from node Ai to node Bi with weight Wi.
But we will connect it the other way round that is Bi -> Ai with weight Wi.
And now we can simply use DFS or BFS.

So here i have used BFS and this function is actually my blackbox.

# Ignore threshold
We will just include one outgoing from my node that result in minimum answer. Suppose from 1 i can reach 0. then i can reach 0 from node 2 either using the edge that connect it to 1 or by directly going to node 0. Whichever result in minimum we will use that. We just have to reach zero. Either directly or indirectly it doesn't matter. Hence we can ignore threshold.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$$O((v+E)log(w))$$
Here V = number of nodes, E = number of edges, W = maximum weight
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(V)$$

Even if we have considered to use the maximum weight in the graph, we cannot satisfy the condition then we will simply return zero.

# Code
```python3 []
class Solution:
    def minMaxWeight(self, n: int, edges: List[List[int]], threshold: int) -> int:
        # reverse graph -> invert the edges
        # check if it is possible to reach all nodes from zero

        max_w=0 # maximum weight
        graph=[list() for _ in range(n)]
        for u,v,w in edges:
            graph[v].append((u,w))
            max_w=max(max_w,w)
        
        def bfs(k):
            # blackbox
            vis=set()
            q=deque([0])
            vis.add(0)
            while q:
                u=q.popleft()

                for v,w in graph[u]:
                    if w<=k and v not in vis:
                        q.append(v)
                        vis.add(v)
                
            return len(vis) == n
        
        low,high,ans=1,max_w,-1

        while low<=high:
            mid=(low+high)//2
            if bfs(mid):
                ans=mid
                high=mid-1
            else:
                low=mid+1
        
        return ans
```
['Binary Search', 'Greedy', 'Depth-First Search', 'Breadth-First Search', 'Graph', 'Shortest Path', 'Minimum Spanning Tree', 'Python3']