無関係な頂点を縮約してから拡張ダイクストラやれば通りそうだが、実装する気力が... orz