Sample input: n=4, m=3, q=5. Edges: (1,2,5), (1,3,9), (2,3,3). Initialize dist: dist[1][2] = dist[2][1] = 5, dist[1][3] = dist[3][1] = 9, dist[2][3] = dist[3][2] = 3, rest infinity. After Floyd-Warshall: dist[1][3] = 8 (route 1→2→3).
Query (1,3) returns 8. This shows how Floyd-Warshall discovers indirect paths that are shorter than direct edges. The algorithm found a better path by routing through vertex 2.