This problem is asking for the shortest distance from node ~1~ to node ~N~ given that you can use ~1~ extra edge from a pile. The naive solution would be to keep a running best and iterate through each edge, add it to the graph, run a shortest path algorithm (Dijkstra's or SPFA?), and then delete it from the graph. Unfortunately, this would not get you all the test cases as it is too slow.

The intended solution was to run Dijkstra's once from node ~1~, then reverse the graph and run Dijkstra's again from node ~N~. After, keep a running best and for each edge,

best = min(best, forw[startingnode] + weightofedge + back[endingnode])

where forw is the array holding minimum distance from node ~1~, back is the array holding minimum distances from node ~N~, startingnode is the first endpoint of the edge, endingnode is the second endpoint of the edge, and weightofedge is its weight.

Why does this work? Well, for an edge to make any difference, it must be a part of the shortest path when we add it to the graph. How do we compute the shortest path including an edge ~e~? Well, any path containing edge ~e~ can be split into three parts: The path from ~1~ to the start of ~e~, the weight of ~e~ itself, and the path from the end of ~e~ to ~N~. To minimize the total distance of this path, we just need to ensure the first and third parts are minimized! Since for any edge, the first part will start from node ~1~, we just need one run of Dijkstra's or SPFA starting at node ~1~ to answer all queries. Since for any edge, the third part will end on node ~N~, we just need one more run of Dijkstra's starting from node ~N~ to answer all the queries (to do this, we need to reverse the edges)!