When you add node k, it becomes a potential intermediate node in paths. Run one iteration of Floyd-Warshall with k as the intermediate:
For all pairs i, j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
This updates all pairs in time. After adding all nodes in reverse order, you have effectively run full Floyd-Warshall and captured the sum at each step. Total time is across all insertions, which fits the constraint.