この問題は，グラフの最短経路長を求めるアルゴリズムの練習問題です．非負の辺重みを持つグラフに対し，ある始点から各頂点への最短経路長は，ダイクストラ法により高速に求めることができます．

この問題では頂点にも重みがあるので，そのままではダイクストラ法を適用できません．そこで，辺のみに重みを持つ問題に言い換えます．

頂点 \(U_j\) にいる状態から辺 \(j\) を使って頂点 \(V_j\) に移動するとき，新たにかかるコストは，「辺 \(j\) を通るコスト」と「頂点 \(V_j\) を通るコスト」の和，すなわち \(B_j + A_{V_j}\) です． 逆に，頂点 \(V_j\) にいる状態から辺 \(j\) を使って頂点 \(U_j\) に移動するとき，新たにかかるコストは，「辺 \(j\) を通るコスト」と「頂点 \(U_j\) を通るコスト」の和，すなわち \(B_j + A_{U_j}\) です．

よって，各辺 \(j\) に対し，\(U_j \to V_j\) の向きに重み \(B_j + A_{V_j}\) の辺を，\(V_j \to U_j\) の向きに重み \(B_j + A_{U_j}\) の辺を張ることで，すべてのコストを辺重みのみで表現できます．この新しいグラフ上でダイクストラ法を実行し，最後に始点の重み \(A_1\) を足すことで，答えを求めることができます．時間計算量は \(O(M \log N)\) です．

実装例 (PyPy)