给一张地图，地图上有一些城市，城市之间可能有线路连通，我们用一个无向图来表示以简化概念，每条边有个权值，表示选择这条边需要花费的费用。给定4对顶点(可能重复)，求一个权值最小的边集，使得任意一对顶点可以由选出的边集中的边相连。 按照惯例，下面给出一个例子：
第1行2个整数，n和m，分别表示城市的个数和边的个数。 接下来n行，每行一个字符串，表示每个城市的名字。城市的名字为一个不超过20个字符，由小写字母构成的字符串。 再接下来m行，每行给出s1s2和w，其中s1s2为城市的名字，w为他们之间边的权值。 最后，给出4行，每行给出两个字符串，分别为要求的一对城市的名字。
10%或20%的数据中，地图是一棵树。
对于所有数据，
n<=30m<=1000w<=10000。