P10601 [NWERC 2006] Ticket to Ride

给一张地图，地图上有一些城市，城市之间可能有线路连通，我们用一个无向图来表示以简化概念，每条边有个权值，表示选择这条边需要花费的费用。给定 $4$ 对顶点（可能重复），求一个权值最小的边集，使得任意一对顶点可以由选出的边集中的边相连。

第一行输入 $2$ 个整数，$n$ 和 $m$，分别表示城市的个数和边的个数。 接下来 $n$ 行，每行一个字符串，表示每个城市的名字。城市的名字为一个不超过 $20$ 个字符，由小写字母构成的字符串。 再接下来 $m$ 行，每行给出 $s_1,s_2,w$，其中 $s_1,s_2$ 为城市的名字，$w$ 为他们之间边的权值。 最后，给出 $4$ 行，每行给出两个字符串，分别为要求的一对城市的名字。

输出一行，输出最小的花费。

数据保证，$1\leq n\leq 30$，$0\leq m\leq 1000$，$1\leq w\leq 10000$。