该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

徐老师最近在玩一个手游，游戏中最近新出了一个活动，击杀活动副本 $BOSS$ 可以获得不同种类的兑换币

为了强行提高用户游戏时长，游戏中的兑换币分为："金币","银币","铜币","纪念币"...以及一种特殊兑换币，"氪币"

字面意思，就是玩家可以花钱充值来购买 "氪币"，活动中一共 $n$ 种兑换币，为了方便描述，我们将其分别编号为 $1 \dots n$，其中 "氪币" 的编号为 $1$

每一种兑换币都拥有自己的兑换界面，可以兑换非常多种类的奖励

徐老师刷了几天活动兑换了一部分奖励，但是他想要的奖励实在是太多而且太杂了，并且刷活动的时间过长，实在是太累了

于是他发现，原来当玩家充值购买 "氪币" 以后会自动开通兑换币转换功能！

兑换币转换功能共有 $m$ 条转换规则，其中第 $i$ 条转换规则可以用三个数字 $x_i,y_i,z_i$ 来描述，表示玩家可以将 $1$ 个 $x_i$ 号兑换币转换成 $10^{z_i}$ 个 $y_i$ 号兑换币

例如 $1 2 1$ 表示可以用 $1$ 个 $1$ 号兑换币转换成 $10$ 个 $2$ 号兑换币

当然， $z_i$ 可以是负数，例如 $1 2 -1$ 表示 $1$ 个 $1$ 号兑换币可以转换成 $10^{-1} = 0.1$ 个 $2$ 号兑换币

现在徐老师已经选好了每个兑换界面他分别需要的奖励，并计算好了每种兑换币的需求量

他想知道他最少需要购买多少 "氪币" 才能兑换到他想要的所有东西？

P.S. 题目保证 "氪币" 一定能直接或间接转换成任意兑换币，并且不存在任意一种货币可以间接或者直接的转换成数量更多的同种货币

输入格式

输入第一行包含两个整数 $n,m$ 表示有 $n$ 种货币，$m$ 条转换规则

接下来一行包含 $n$ 个数字，表示徐老师需要每种兑换币的数量 $a_i$

接下来 $m$ 行，每行三个整数 $x_i,y_i,z_i$ 表示一条兑换币转换规则
对于 $10\%$ 的数据，所有兑换关系满足 $z=0$
对于再 $30\%$ 的数据，$n \leq 100$
对于 $20\%$ 的数据，答案不超过 $10^9$
对于 $30\%$ 的数据，$m=n−1$
对于 $60\%$ 的数据，所有兑换关系满足 $z \leq 0$
对于 $100\%$ 的数据，$n \leq 10^5, m \leq 2 * 10^5, 0 \leq a_i \leq 2147483647, −1000 \leq z \leq 1000$

特别的保证：答案不会超过 $10^{10000}$

输出格式

输出徐老师最少需要购买的 "氪币" 数量，这个数量可能是浮点数，请四舍五入保留到小数点后 $6$ 位

样例

3 2
1 1 1
1 2 1
2 3 1

1.110000