说明

穗织镇的法定货币是穗织币。除了穗织币，地球上还有许多可以充当货币的物品，例如美刀、祟神碎片、茉子币... 共有n种，穗织币是第1种。 

有些货币可以兑换成其他的货币，但不一定是双向的。 

例如 1 茉子币可以氪出100个钻石，但不能用100钻石兑换1茉子币.。

纵观整个穗织镇，共有m种货币兑换的关系。

为了去全世界旅游，大李和豆豆难免遇到各种谜题。现在他们需要集齐一定数量的各种货币，且第i种货币需要ai个，而现在他们除了穗织币什么也没有。

保证所有货币都能通过穗织币直接或间接兑换，请帮大李和豆豆计算出最少需要多少穗织币可以满足要求。

输入格式

第一行两个整数n和m。 

接下来一行n个数字，第i个数字表示解开谜题需要第i种货币的数量。 

接下来m行每行三个整数 x, y, z，表示1个x可以兑换10z个y。(10的z次方)

输出格式

一个浮点数，最少需要多少穗织币可以解决谜题，保留6位小数。

样例

3 2
1 1 1
1 2 1
2 3 1

1.110000

提示

数据范围 

对于10%的数据，所有兑换关系满足z=0。 

对于再30%的数据，n≤100。

对于20%的数据，答案不超过10⁹。 

对于30%的数据，m=n−1。 

对于60%的数据，所有兑换关系满足z≤0。 

对于100%的数据，n≤10⁵, m≤2×10⁵, 0≤ai≤2147483647, −1000≤z≤1000, 答案不超过1010000。 

保证不存在一条货币兑换的路径，使得一定数量的某种货币经过一系列兑换变为更多数量的同种货币。