Codeforces 295B Greg and Graph - Floyd-Warshall Incremental

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 $O(N^2)$ 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 $O(N^3)$ across all insertions, which fits the constraint.