3669: 征服-【2014暑期训练】T1Day2选讲（陈泽天）
Memory Limit：256 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：1
Description
征服
背景
I came, I saw, I conquered！—MY【题目描述】
MY带着他的军队来到了一个叫作Xiang的国家！Xiang由N个城市组成，部分城市之间有通道（双向），欲想征服这个国家，必须占领所有城市！战争必会带来损伤！求征服Xiang的最小的代价！
有两种战略可以实施：
1.可以选个任意城市i，从空中投放士兵占领，代价为fly[i]；
2.在已经占领的城市u向周围扩张! 若u与v有路相连，可付出road(u,v)代价,占领据点v，（此时不用付出代价fly[i]）。
【输入格式】
第一行包含2个整数：据点数N（1≤N≤10000），通道数(0≤M≤100000)；
接下来有M+1行，
第二行有N个数：第i个数fly[i]（1≤fly[i]≤100000）,为占领第i个据点的代价；
接下来有M行，每行代表一条通道包含3个整数：a,b,c（1≤a≤N,1≤b≤N,1≤c≤100000）， 表示据点a与据点b之间有通道相连，通过所需代价为c！(注意：可能出现重边)
【输出格式】输出包括一行，征服Xiang的最小的代价！形式如下面样例所示。
【样例输入】
3 2
10 1 10
1 2 1
2 3 1
【样例输出】
3
HINT
增加一个虚拟的点，对每一个结点连接一条边，边的权值为fly[i]，然后对整个图求最小生成树。