For any two nodes u and v, let d(u, v) be the smallest time cost among the paths connecting u and v.