(10%) Consider the given directed graph.

The Floyd-Warshall algorithm can solve the all-pairs shortest-paths problem on a directed graph $G = (V, E)$. Answer the following questions.

(1) (2%) What is the time complexity of Floyd-Warshall algorithm?

(2) (3%) Let $d_{ij}^{(k)}$ be the weight of a shortest path from vertex $i$ to vertex $j$ for which all intermediate vertices are in the set $\{1,2,...,k\}$ and $D^{(k)} = \left(d_{ij}^{(k)}\right)$ be a $n \times n$ matrix. Floyd-Warshall algorithm computes $D^{(k)}$ from $D^{(k-1)}$ as the following formula.

$d_{ij}^{(k)} =$ ________________

Please complete the above formula.

(3) (5%) Let $dist(i,j)$ be the length of the shortest path from node $i$ to node $j$. What is $dist(1,5) + dist(2,5) + dist(3,5) + dist(4,5) + dist(6,5)$?