最小生成树——垃圾佬抓宠物

垃圾佬抓宠物
TimeLimit:1000MS  MemoryLimit:128MB
64-bit integer IO format:%lld

Problem Description
垃圾佬也有头痛的时候，这不，垃圾佬的GF又缠着他了……

静静：“Darling！”
垃圾佬：“怎么？”
静静：“我玩那个OWO更新了哦~新增的宠物系统好可爱啊~不过抓宠物要用好多魔法豆哎”
垃圾佬：“那个魔法豆是打怪得的?”
静静："不是哦，用RMB 买才得。"
垃圾佬：“哎，现在的网游，就是会骗钱。”
静静：“怎么能这么说人家呢，那些宠物都好可爱的，花点钱算什么嘛。我打算把所有的宠物都抓到哦~”
垃圾佬：“又说没有魔法豆，难道……”
静静：“我把你的钱都拿来冲成魔法豆了哦~你看你看，这些宠物都好可爱的，你不会有意见吧?^_^”
垃圾佬：“……没有。”
静静：“不要苦瓜着脸嘛，要不这样吧，你帮我把所有的宠物都抓起来，剩下的魔法豆我再帮你换回RMB 好不好?^_^”
垃圾佬：“……好……好吧”

这下惨了，垃圾佬现在好后悔在静静面前炫耀自己的钱包啊……
静静做事，向来说一不二，抓齐宠物恐怕是免不了的了。
不过，垃圾佬发现，这个网游的抓宠物系统是这样设定的：
抓特定的某种宠物需要花费特定的魔法豆。
另外，还可以通过一种宠物的呼唤能力来抓取另一种宠物，当然，要让宠物发挥它的呼唤能力需要两个条件：
    第一，它要是你的宠物……人家还野生呢总不会听你的话陷害好友吧。
    第二，你需要喂给你的宠物一定的魔法豆，它才有力气施展它的能力。
当另一只宠物被呼唤过来之后，你不费什么力气就可以把它抓住，也就不必再向系统付额外的魔法豆了。
注意，一种宠物能呼唤另一种宠物是因为他们心灵相通，所以如果A宠物能呼唤B宠物，那么B宠物也一定能呼唤A宠物。
而且，垃圾佬仔细研究之后发现，可能是OWO的程序员懒得再设置数据，A 宠物呼唤B宠物需要的魔法豆和B宠物呼唤A宠物需要的魔法豆是相等的。
垃圾佬的目标，当然是要算出最少要花费多少魔法豆啦~
垃圾佬拿出纸笔，算啊算啊算啊算，就在垃圾佬算出来的一刹那，静静温柔的对垃圾佬说：“Darling，你会不会觉得我很败家啊……其实我也知道我不应该用你的钱来冲魔法豆的”
垃圾佬心中一喜，抬头看着静静，静静说：“要不你不用抓齐，少抓一只吧。”
垃圾佬呆住了……这是一个多么体贴的GF啊!许久许久，垃圾佬又拿起纸笔重新算过。
Input
第一行一个数字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

Output
只有一行，满足MM 需求最少要花费多少魔法
SampleInput
3
10 10 10
3
1 2 7
1 3 1
2 3 3
SampleOutput
11

样例说明：先抓第一只，然后用第一只呼唤第三只。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define N 255
int p[N], b[N];
struct edge
{
    int from, to, w;
}e[90000];
struct node
{
    int w, vis;
}a[N];
int cmp(const edge& a, const edge& b)
{
    return a.w < b.w;
}
int find(int x)
{
    if (x != p[x])
        p[x] = find(p[x]);
    return p[x];
}
int join(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y)
        return 0;
    p[x] = y;
    return 1;
}
int main(void)
{
    int n, nn = 2147483647;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i].w);
        if (a[i].w < nn)
            nn = a[i].w;
        p[i] = i;
    }
    int m; scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &e[i].from, &e[i].to, &e[i].w);
    }
    sort(e + 1, e + m + 1, cmp);
    int f = 0;
    if (n - 2 <= m)
    {
        m = n - 2;
        f = 1;
    }
    else
        m = n - 1;
    int sum = 0, t = 0;
    for (int i = 1; i <= m; i++)
    {
        if (join(e[i].from, e[i].to))
        {
            sum += e[i].w;
            a[e[i].from].vis = a[e[i].to].vis = 1;
        }
    }
    if (f)
    {
        printf("%d\n", sum + nn);
        system("pause");
        return 0;
    }
    int bb = 0; nn = 2147483647;
    for (int i = 1; i <= n; i++)
    {
        if (a[i].vis == 0)
            b[++bb] = a[i].w;
        if (a[i].vis == 1)
            if (a[i].w < nn)
                nn = a[i].w;
    }
    sort(b + 1, b + bb + 1);
    for (int i = 1; i <= bb - 1; i++)
    {
        sum += b[i];
    }
    printf("%d\n", sum + nn);

    system("pause");
    return 0;
}
/*
4
1 2 3 4
1
2 3 1
3

5
1 2 3 4 5
2
1 2 1
1 3 1

5
1 2 3 4 5
6
1 2 1
1 3 1
1 4 1
1 5 1
2 3 2
3 4 3
*/