This problem teaches you that precomputation wins when you have many queries.
Instead of running Dijkstra times, run Floyd-Warshall once and answer queries in . This pattern applies to many problems: if you can afford preprocessing, you can answer all-pairs queries immediately. The core insight is recognizing when the query count justifies expensive preprocessing. If , Floyd-Warshall is usually the right choice.