家财万贯，拥有全世界$99\%$矿坑的$FTY$打算打造一个属于自己的国度，她将这个国度命名为“天国”。天国一共有$n$个城市，一开始所有的城市两两之间都是不连通的。

$FTY$打算建造一些“天路”以让整个天国连通。$FTY$一共有$m$条天路可供选择建造，建造第$i$条天路将连接$a_i$和$b_i$两个城市，并花费$c_i$的代价。现在$FTY$想从这$m$条天路中选出恰好$n-1$条天路建造以使得$n个$城市可以两两互相到达。

当天国连通以后，每个城市都会带来一定的收益。具体地，若第$i$个城市连接了$k_i$条天路，将会提供$d_i\times k_i$的收益。

现在$FTY$想要让利益最大化，即使得(建造天路的总代价-所有城市带来的收益)这个值尽量的小。

身为一个精明的矿主，她花费$10^{-10^{10000}}$津巴布韦元雇佣你帮她解决这个问题，请你把这个值告诉$FTY$。

第一行两个整数$n(1\leq n \leq 1000)$和$m(1\leq m\leq 3000)$，表示天国中城市的数量和天路的数量。

接下来一行$n$个整数，第$i$个整数表示$d_i(1\leq d_i\leq 10^8)$。

接下来$m$行每一行三个整数表示$a_i,b_i(1\leq a_i,b_i\leq n)$和$c_i(1\leq c_i\leq 2\times 10^8)$。

输出一个整数，表示(建造天路的总代价-所有城市带来的收益)的最小值（注意答案可能为负数）。

若不存在某种建造方案，使得天国中的城市两两可互相到达，请输出"FTYYYDS!!!"（不含双引号）。