Problem Link

My solution

My approach:

I applied Binary search on Mean(i.e answer to be found) and assigned weight of each edge equal to [Val-Mid] (Val is the value of each egde in the initial graph and Mid is the present Value of Mean during the binary search).

For each Mid in binary search I applied Bellman ford to check if any negative value cycle exists. I am constantly getting WA.(i even tried floyd for negative cycle detection).

Any help is appreciated.