\(N\) 個の街と \(M\) 個の道は、 \(N\) 頂点 \(M\) 辺の重み付き無向グラフとしてとらえることができます。頂点 \(S\) からの最短距離と頂点 \(T\) からの最短距離が等しいような頂点が答えとなります。

最短距離はダイクストラ法で求めることができます。（資料は検索すればたくさん出てくるため詳細は省略します）

なお、問題文で与えられるグラフが連結ではないケースがあることに注意してください。答えとなる頂点は、頂点 \(S,T\) 両方と連結である必要があります。