町を頂点、道路を辺とすると最短経路問題に近いですが、ワープを再現する辺を愚直に張ると辺の数が \(\Theta(N^2)\) 本になって TLE になります。
ここで以下のような辺の張り方をします。

• 新たな \(6\) つの頂点 \(\mathrm{A_{in}}, \mathrm{B_{in}}, \mathrm{C_{in}}, \mathrm{A_{out}}, \mathrm{B_{out}}, \mathrm{C_{out}}\) を作る。
• すべてのタイプ A のワープ台を持つ町について、その町に対応する頂点から \(\mathrm{A_{in}}\) へ、コスト \(0\) の有向辺を張る
• すべてのタイプ B のワープ台を持つ町について、その町に対応する頂点から \(\mathrm{B_{in}}\) へ、コスト \(0\) の有向辺を張る
• すべてのタイプ C のワープ台を持つ町について、その町に対応する頂点から \(\mathrm{C_{in}}\) へ、コスト \(0\) の有向辺を張る
• \(\mathrm{A_{in}}\) から \(\mathrm{B_{out}}\) へコスト \(X_{\mathrm{AB}}\) の有向辺を張る。
• \(\mathrm{A_{in}}\) から \(\mathrm{C_{out}}\) へコスト \(X_{\mathrm{AC}}\) の有向辺を張る。
• \(\mathrm{B_{in}}\) から \(\mathrm{A_{out}}\) へコスト \(X_{\mathrm{AB}}\) の有向辺を張る。
• \(\mathrm{B_{in}}\) から \(\mathrm{C_{out}}\) へコスト \(X_{\mathrm{BC}}\) の有向辺を張る。
• \(\mathrm{C_{in}}\) から \(\mathrm{A_{out}}\) へコスト \(X_{\mathrm{AC}}\) の有向辺を張る。
• \(\mathrm{C_{in}}\) から \(\mathrm{B_{out}}\) へコスト \(X_{\mathrm{BC}}\) の有向辺を張る。
• すべてのタイプ A のワープ台を持つ町について、 \(\mathrm{A_{out}}\) からその町に対応する頂点 へ、コスト \(0\) の有向辺を張る
• すべてのタイプ B のワープ台を持つ町について、 \(\mathrm{B_{out}}\) からその町に対応する頂点 へ、コスト \(0\) の有向辺を張る
• すべてのタイプ C のワープ台を持つ町について、 \(\mathrm{C_{out}}\) からその町に対応する頂点 へ、コスト \(0\) の有向辺を張る

これが正しくワープを再現していること、頂点数が \(O(N)\) で辺数が合計で \(O(N + M)\) に収まっていることは明らかです。
よってこのグラフ上でダイクストラ法で最短経路長を求めれば、\(O((N + M) \log(N + M))\) で答えが求まります。