3258: 喜欢宠物的GF

 小烈现在好后悔在MM 面前炫耀自己的钱包啊……MM 做事，向来说一不二，抓齐宠物恐怕是免不了的了。不过，小烈发现，这个网游的抓宠物系统是这样设定的：    抓特定的某种宠物需要花费特定的魔法豆。另外，还可以通过一种宠物的呼唤能力来抓取另一种宠物，当然，要让宠物发挥它的呼唤能力需要两个条件：    第一，它要是你的宠物……    第二，你需要喂给你的宠物一定的魔法豆，它才有力气施展它的能力。    当另一只宠物被呼唤过来之后，你不费什么力气就可以把它抓住，也就不必再向系统付额外的魔法豆了。    注意，一种宠物能呼唤另一种宠物是因为他们心灵相通，所以如果 A 宠物能呼唤 B 宠物，B 宠物也一定能呼唤 A 宠物。而且， A 宠物呼唤 B 宠物需要的魔法豆和 B 宠物呼唤 A 宠物需要的魔法豆是相等的。小烈的目标，当然是要算出最少要花费多少魔法豆啦~    小烈拿出纸笔，算啊算啊算啊算，就在小烈算出来的一刹那，MM 温柔的对小烈说：“烈烈，你会不会觉得我很败家啊……其实我也知道我不应该用你的钱来冲魔法豆的”小烈心中一喜，抬头看着 MM，MM 说：“要不你不用抓齐，少抓一只吧。”    小烈呆住了……这是一个多么体贴的 GF 啊!许久许久，小烈又拿起纸笔重新算过。

   第一行 一个数字 n，代表网游里一共有 n 种宠物。    第二行有 n 个数字，用空格隔开，依次说明直接抓取第 1，2，3，4……n 种宠物需要多少魔法豆    第三行一个 C，表示游戏一共设定了 C 对宠物心灵相通，可以互相呼唤。    接下来 C 行，每行都有三个数字 a，b 和 w。代表第 a 种和第 b 种宠物可以互相呼唤，呼唤前需要给 a 宠物或 b 宠物喂 w 魔法豆。

    只有一行，满足 MM 需求最少要花费多少魔法豆。

    3
    10 10 10
    3
    1 2 7
    1 3 1
    2 3 3

11