Do you know that there is a Bear Island in Antarctica? Barr the Bear has landed on Bear Island and is looking to invade Poe the Penguins homeland. He has created bases in n islands, including Bear Island (we will label islands from 1 to n, where Bear Island is labeled as 1). Barr has also constructed m bidirectional transit lines between the islands for his covert operations. The line connecting island i and island j takes wij minutes to traverse and (coincidentally) costs wij Barr coins per hour to maintain. For each of the transit lines, wij > 0. Let di be the shortest time it takes to traverse from Bear Island to island i. Barr the Bear spent too much money on honey and is running low on coins. He decides that he wants to close down some transit lines to save coins. However, he still wants to ensure that closing down transit lines will not affect the shortest amount of time to travel from Bear Island to each island (that is, even after closing down transit lines, di would still be the same). Given n islands, the list of m transit lines, and their costs, help Barr the Bear find a subset of transit lines such that the cost of maintaining the lines is minimized (the total number of coins to be spent per hour), and yet the time taken to travel from Barr Island to every other island remains the same as before closing down any lines. Solve the problem in O(m+n log n) time. Your algorithm should output which transit lines are remaining (or which ones to be removed, equivalently). Prove correctness and analyze runtime. If you are using a graph formulation, remember to explicitly state what is the graph you are using (e.g., what are the vertices and edges).