Add nodes in reverse deletion order:
order = reverse of deletion order
dist = 2D array, all infinity
added = array, all false
answers = empty list
for k in order:
added[k] = true
dist[k][k] = 0
for i where added[i]:
dist[i][k] = adj[i][k]
dist[k][i] = adj[k][i]
for i where added[i]:
for j where added[j]:
dist[i][k] = min(dist[i][k], dist[i][j] + adj[j][k])
dist[k][i] = min(dist[k][i], adj[k][j] + dist[j][i])
for i where added[i]:
for j where added[j]:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
sum = 0
for i where added[i]:
for j where added[j]:
sum = sum + dist[i][j]
answers.append(sum)
print reverse of answers