013 - Passing（★5）
頂点
$ k
を通る最短経路は
$ d(1,k)+d(k,N)
に等しい
$ 1, N
それぞれを始点にしたダイクストラを行う
https://atcoder.jp/contests/typical90/submissions/59020980