HERO国家遭受其他国家的攻击。入侵者正在攻击首都，因此其他城市必须向首都派遣支援。城市之间有一些道路，货物必须沿着这些道路运输。

根据道路的长度和货物的重量，运输过程中会产生一些成本。每条道路的成本率是指运输在该道路上的货物的成本与重量的比率。保证成本率小于1。

另一方面，每个城市必须等待所有货物到达，然后将到达的货物与自己的货物一起运送到下一个城市。一个城市只能将货物运送到一个城市。

你的任务是找到能够到达首都的货物的最大重量。

有多个测试用例。

对于每个测试用例，在第一行中有两个整数 N（2 \le N \le 100）和 M，其中 N 是包括首都在内的城市数量（首都标记为 N，其他城市从 1 到 N-1 标记），M 是道路数量。

然后是 N-1 行。第 i 行（1 \le i \le N - 1）包含一个正整数（\le 5000），表示第 i 个城市将运送到首都的货物重量。

接下来的 M 行表示 M 条道路。每行有三个数字 A、B 和 C，表示城市 A 和城市 B 之间有一条道路，该道路的成本率为 C。

处理到文件末尾。

对于每个测试用例，在一行中输出可以运送到首都的最大重量，精确到小数点后两位。