Construct the graph, treating \(0\) as a separate vertex. Let \(dist_{u, v}\) be the distance between \(u\) and \(v\) on this graph (which might be \(\infty\) if there is no path)

Then the answer for \(i\) is equivalent to the distance between \(1\) and \(N\) if a special edge of cost \(0\) is added between vertices \(0\) and \(i\). If this edge isn’t used, the distance is still \(dist_{1, N}\), otherwise it’s \(\min (dist_{1, 0} + dist_{i, N}, dist_{1, i} + dist_{0, N})\). Just pick the minimum value.

Note that all required distances have \(1\) or \(N\) as an endpoint. Thus we can find them by running breadth-first-search twice on the graph.

Thus the problem is solved in time \(O(N + M)\). Be careful of the handling of infinite distances, it may overflow depending on implementation.