Company: Zorvyn SDE_3april
Difficulty: medium
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 First line contains three space-separated integers N , M , and K . Next M lines each contain three integers u , v , w representing a road between cities u and v with travel time w . Next K lines each contain two integers a , b representing a magical bridge between cities a and b . Output Format Print a single integer - the minimum time to reach city N from city 1. If it is impossible to reach city N, print -1. Examples Exam