有N个城市和N-1条道路的国家，每个城市编号为1,2,...,N。

城市Ai和城市Bi之间有双向道路，长度Ci。

如果没有道路将城市i和城市j直接连接，则添加一条直接连接城市i和城市j的长度为X的道路。

对于所有满足1≤i<j≤N的两个城市i和j，用d(i,j)表示从城市u到城市v的最短距离。要求输出所有的d(u,v)总和。

样例解释描述了城市与道路之间的关系。蓝色实线表示原始的N-1条路径，黑色虚线表示由操作新添加的长度3的路径。