T571496 結束乐队

“为什么……为什么要演奏春日影？！” 她的声音突然在空旷的休息室中响起，带着一丝颤抖和愤怒，她的眼神中充满了无助与痛苦，仿佛那首曲子触动了某个深埋已久的伤口。这句话像是一把利刃，划破了原本跳跃着的空气。 她不愿意承认，那段快乐的日子永远停留在了过往，复辟库来西库终归只能是她的一厢情愿。 Crychic，已经不在了。 拖着贝斯，她缓步离开RiNG，淹没在夜色中。 …… "该醒了。"她对着虚空呢喃，手机缓缓从手中滑落，仿佛永远也得不到回复的对话框闪烁着，逐渐黯淡了。 她在迷途上走的太远了，终于到了不得不面对的时候。 她苦苦追寻着的那段转瞬即逝的梦，最终还是要破灭了。 “既然这样的话，就让我来亲手结束它。”她仰起头，坚定的眼神望向对面的那位粉发少女，那个本该是梦境引子的女人。 

你是来亲手结束这个乐队的，M团共有$n$个人($n\le 1000$)，每个人都可以被收买，被收买的代价估算为$c_i$。M团的队员之间有$m$对朋友关系，第i对朋友为$x_i,y_i$，如果他们两人间有一人已被收买，那么只需要花费$z_i$的代价即可收买另一人。 收买$n$个乐队成员才可使得乐队解散 你想知道亲手结束这个乐队需要花费的最小代价是多少

第一行，输入2个正整数$n,m$ 第二行，输入$n$个正整数$c_i$，表示你收买每个人的代价 接下来m行，每行三个正整数数$x_i,y_i,z_i$，表示一对朋友关系

输出一行，一个正整数，表示亲手结束这个乐队的最小代价。

对于20%的数据，$n\le 10,m \le 20$ 对于100%的数据，$n\le 1000,m\le 200000$ $1\le c_i,z_i\le 10^6,1\le x_i,y_i \le n$