Time Limit: 1000 MS    Memory Limit: 131072 K 


Description

川大有n个围合,编号为1到n。每个围合里都会有着一为大神。连接这些围合的有P条道路,每条道路都是双向的,第j条道路连接了牧场Sj和Ej,通行需要Lj的时间。 约翰打算在保持各牧场完全联通的情况下去掉斤两多的道路。 校长知道,在道路被强拆后,大神们会非常伤心,所以他计划拆除完道路之后就去忽悠他们。他可以从任意一个牧场开始的他的维稳工作。当他走访完所有的奶牛之后,还要回到他的出发地。 每次路过围合i,他必须花Ci的时间大神们交谈,即使之前已经做过工作了,也要留下来再谈一次。注意他在出发和回去的时候,都要和该地的大神们交谈一下。 请你计算一下,他在忽悠大神之前,选择拆除哪些道路,才能让忽悠大神这事的时间画的最少?

Input

有多组输入。 对于每组数据 第一行: 两个整数N、P,5<=N<=10000,N-1<=P<=10^5 第二行到第N+1行: 第i+1行有一个整数Ci,1<=Ci<=1000 第N+2行到N+P+1行:第N+j+1行包括三个整数Sj,Ej,Lj,1<=Sj,Ej<=N, Sj≠Ej,0<=Lj<=1000

Output

每组数据输出一个整数,表示忽悠所有大神需要的最少时间

Sample Input

5 7 10 10 20 6 30 1 2 5 2 3 5 2 4 12 3 4 17 2 5 15 3 5 6 4 5 12

Sample Output

176