You are given an undirected weighted connected graph with n vertices and m edges without loops and multiple edges. The i-th edge is ei=(ui,vi,wi); the distance between vertices ui and vi along the ed