Magical Bridges

Problem Statement

In the kingdom of Algorithmia, there are N cities numbered from 1 to N , connected by M bidirectional roads. Each road has a certain travel time associated with it. The kingdom also has K magical bridges. Each magical bridge connects two cities and has zero travel time, but each magical bridge can only be used once during your entire journey. You cannot use more than K magical bridges in total. You are a traveler starting from city 1 and want to reach city N . Find the minimum time required to travel from city 1 to city N using at most K magical bridges. Input Format You are given three integers N , M , and K , representing the number of cities, the number of bidirectional roads, and the total number of magical bridges available, respectively. You are also given two 2D arrays: roads , where roads[i] = [u, v, w] indicates a bidirectional road between city u and city v with a travel time of w . bridges , where bridges[i] = [a, b] indicates a magical bridge connecting city a and city b wi