ZYB's playground can be described as an undirected connected graph G withn nodes named from 1 to n and m edges. ZYB wants to jump between all pairs (i,j). If he starts at i,and wants to finish at j, he will choose the path for which the second longest edge is smallest, and denote its length asD(i,j). Besides,if a path contains only one edge, the length of second longest edge will be 0.For example, if there 4 nodes and 4 edges ,,, and ZYB wants to jump from 1 and finish at 4. There are two possible paths 1-2-4,1-3-4, thus ZYB will choose 1-3-4 and D(1,4) will be 2.
ZYB likes doing exercises, especially playing basketball. ZYB's playground can be described as an undirected connected graph G with n nodes named from 1 to n and m edges (x_i,y_i,w_i) (x i ,y i ,w i ),where w_i w i is the length for this edge. ZYB wants to jump between all pairs (i,j). If he starts at i,and wants to finish at j, he will choose the path for which the second longest edge is smallest, and denote its length as D(i,j). Besides, if a path contains only one edge, the length of second longest edge will be 0. For example, if there 4 nodes and 4 edges (1,2,3),(2,4,4),(1,3,5),(3,4,2) and ZYB wants to jump from 1 and finish at 4. There are two possible paths 1-2-4(value=3),1-3-4(value=2), thus ZYB will choose 1-3-4 and D(1,4) will be 2. Now ZYB wants to calculate sum_{i=1}^{n}sum_{j=i+1}^{n}D(i,j) ∑ i=1 n ∑ j=i+1 n D(i,j), please help him.
