Build a directed graph with \(2N\) vertices and \(N + M\) edges (costs assigned to edges only) as follows, and the answer is the minimum cost of a path from vertex \(1_\text{in}\) to vertex \(i_\text{out}\).

• For each vertex \(i\) in the original graph, create two vertices \(i_\text{in}\) and \(i_\text{out}\), and add a directed edge \(i_\text{in} \to i_\text{out}\) with cost \(A_i\).
• For each edge \(u \leftrightarrow v\) in the original graph, add two directed edges \(u_\text{out} \to v_\text{in}\) and \(v_\text{out} \to u_\text{in}\) with the same cost.

This minimum cost can be computed using Dijkstra’s algorithm in \(O(M \log N)\) time. (Although the constant factor is larger than the official solution, this method can be used for other purposes as well.)