This problem can be regarded as a single-source shortest paths problem.

For example, in Sample Input 1, we are asked to find the shortest path from Vertex “高橋” (reads Takahashi, in the center of the diagram) to each of the other vertices. Therefore, the problem could be solved in a total of \(O(N\log N)\) time with Dijkstra’s algorithm.