Connecting and disconnecting roads gives a hint to using DSU, also finding the minimum number of coins gives a hint to binary search.

First thing we notice is that blocking all roads would be valid, now to construct the solution, we will use binary search on answer, it will work because if we blocked all roads that costs $$$X$$$ or less and it was valid, blocking all roads that costs $$$X + 1$$$ or less would be valid too.

So for each mid point in the binary search, we can check if the current cost is valid or not by connecting components in DSU when an edge cost is more than the current cost we are checking (the more we block the better, so we should not be choosy about what to block or not, if we can block a road then it is either would not change anything or it would disconnect two cities from each other), after that, we can check for connectivity for all forbidden pairs (cities in feuds), if all pairs were disconnected, then the current cost is valid and we search for less, if not, the current cost is invalid and we should search for a higher cost.

Solution Complixity: $$$O(log(10 ^ 9) * m * log(n))$$$