垃圾佬也有头痛的时候，这不，垃圾佬的GF又缠着他了……
静静：“Darling！”
垃圾佬：“怎么？”
静静：“我玩那个OWO更新了哦~新增的宠物系统好可爱啊~不过抓宠物要用好多魔法豆哎”
垃圾佬：“那个魔法豆是打怪得的?”
静静："不是哦，用RMB 买才得。"
垃圾佬：“哎，现在的网游，就是会骗钱。”
静静：“怎么能这么说人家呢，那些宠物都好可爱的，花点钱算什么嘛。我打算把所有的宠物都抓到哦~”
垃圾佬：“又说没有魔法豆，难道……”
静静：“我把你的钱都拿来冲成魔法豆了哦~你看你看，这些宠物都好可爱的，你不会有意见吧?^_^”
垃圾佬：“……没有。”
静静：“不要苦瓜着脸嘛，要不这样吧，你帮我把所有的宠物都抓起来，剩下的魔法豆我再帮你换回RMB 好不好?^_^”
垃圾佬：“……好……好吧”
这下惨了，垃圾佬现在好后悔在静静面前炫耀自己的钱包啊……
静静做事，向来说一不二，抓齐宠物恐怕是免不了的了。
不过，垃圾佬发现，这个网游的抓宠物系统是这样设定的：
抓特定的某种宠物需要花费特定的魔法豆。
另外，还可以通过一种宠物的呼唤能力来抓取另一种宠物，当然，要让宠物发挥它的呼唤能力需要两个条件：
第一，它要是你的宠物……人家还野生呢总不会听你的话陷害好友吧。
第二，你需要喂给你的宠物一定的魔法豆，它才有力气施展它的能力。
当另一只宠物被呼唤过来之后，你不费什么力气就可以把它抓住，也就不必再向系统付额外的魔法豆了。
注意，一种宠物能呼唤另一种宠物是因为他们心灵相通，所以如果A宠物能呼唤B宠物，那么B宠物也一定能呼唤A宠物。
而且，垃圾佬仔细研究之后发现，可能是OWO的程序员懒得再设置数据，A 宠物呼唤B宠物需要的魔法豆和B宠物呼唤A宠物需要的魔法豆是相等的。
垃圾佬的目标，当然是要算出最少要花费多少魔法豆啦~
垃圾佬拿出纸笔，算啊算啊算啊算，就在垃圾佬算出来的一刹那，静静温柔的对垃圾佬说：“Darling，你会不会觉得我很败家啊……其实我也知道我不应该用你的钱来冲魔法豆的”
垃圾佬心中一喜，抬头看着静静，静静说：“要不你不用抓齐，少抓一只吧。”
垃圾佬呆住了……这是一个多么体贴的GF啊!许久许久，垃圾佬又拿起纸笔重新算过。
第一行一个数字n，代表网游里一共有n 种宠物。
第二行有n 个数字，用空格隔开，依次说明直接抓取第1，2，3，4……n 种宠物需要多
少魔法豆
第三行一个C，表示游戏一共设定了C 对宠物心灵相通，可以互相呼唤。
接下来C 行，每行都有三个数字a，b 和w。代表第a 种和第b 种宠物可以互相呼唤，
呼唤前需要给a 宠物或b 宠物喂w 魔法豆。
n≤250，n∈N+
0<=c<=n*(n-1)/2
所有数字（含结果）<2^31
只有一行，满足MM 需求最少要花费多少魔法
3 10 10 10 3 1 2 7 1 3 1 2 3 3
11样例说明：先抓第一只，然后用第一只呼唤第三只。