頂点 \(v_i\) を, チケットを使わずにたどりついた頂点 \(v_{i, 1}\) とチケットを使ってたどりついた頂点 \(v_{i, 2}\) の2種類に分ける.

\(v_1\) 同士, \(v_2\) 同士は普通にグラフを作成し, それとは別に \(v_{a_i, 1}\) と \(v_{b_i, 2}\) の間に距離 \(0\) の有向辺を追加する. \(v_{b_i, 1}\) と \(v_{a_i, 2}\) の間も同様である.

さらに \(v_{1, 1}\) と \(v_{1, 2}\) の間も特別に距離 \(0\) の有向辺を追加しておく.

これで dijkstra 法を使えばチケットを使わなかった場合の最短距離とチケットを使った場合の最短距離が出るので, この和が答えとなる.