The solution covered in this editorial will use dijkstra's and binary search.

Write a function that takes an argument ~X~ and returns whether the shortest path between any two nodes is less than ~K~ after all the edges have been reduced by ~X~.

Since ~N \le 400~, it is sufficient for the function to run dijkstra's ~N~ times, where each time a new starting node is chosen. If the shortest path from a node ~u~ to another node ~v~ is greater than ~K~, then the function should return false. If the shortest path between any two nodes is less than ~K~, then the function should return true.

Now, we binary search for the answer. If the function returns true for a particular value of ~X~, then our upper bound decreases. If the function returns false for a particular value of ~X~, then our lower bound increases.

Time Complexity: ~O(logK \times N \times(N+MlogN))~