{"raw_statement":[{"iden":"statement","content":"给一张地图，地图上有一些城市，城市之间可能有线路连通，我们用一个无向图来表示以简化概念，每条边有个权值，表示选择这条边需要花费的费用。给定 $4$ 对顶点（可能重复），求一个权值最小的边集，使得任意一对顶点可以由选出的边集中的边相连。"},{"iden":"input","content":"第一行输入 $2$ 个整数，$n$ 和 $m$，分别表示城市的个数和边的个数。\n\n接下来 $n$ 行，每行一个字符串，表示每个城市的名字。城市的名字为一个不超过 $20$ 个字符，由小写字母构成的字符串。\n\n再接下来 $m$ 行，每行给出 $s_1,s_2,w$，其中 $s_1,s_2$ 为城市的名字，$w$ 为他们之间边的权值。\n\n最后，给出 $4$ 行，每行给出两个字符串，分别为要求的一对城市的名字。"},{"iden":"output","content":"输出一行，输出最小的花费。"},{"iden":"note","content":"数据保证，$1\\leq n\\leq 30$，$0\\leq m\\leq 1000$，$1\\leq w\\leq 10000$。"}],"translated_statement":null,"sample_group":[["10 15\nstockholm\namsterdam\nlondon\nberlin\ncopenhagen\noslo\nhelsinki\ndublin\nreykjavik\nbrussels\noslo stockholm 415\nstockholm helsinki 396\noslo london 1153\noslo copenhagen 485\nstockholm copenhagen 522\ncopenhagen berlin 354\ncopenhagen amsterdam 622\nhelsinki berlin 1107\nlondon amsterdam 356\nberlin amsterdam 575\nlondon dublin 463\nreykjavik dublin 1498\nreykjavik oslo 1748\nlondon brussels 318\nbrussels amsterdam 173\nstockholm amsterdam\noslo london\nreykjavik dublin\nbrussels helsinki","3907"],["2 1\nfirst\nsecond\nfirst second 10\nfirst first\nfirst first\nsecond first\nfirst first","10"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}