Byteotia 以其丰富的黄金矿藏而闻名。因此，多年来，该国一直向邻国 Bitland 出售黄金。不幸的是，日益增长的财政赤字迫使 Bitland 国王对金属和矿物征收高额关税。跨境贸易商必须支付运输货物价值 $50\%$ 的关税。Byteotia 的商人们面临破产的威胁。幸运的是，Byteotia 的炼金术士已经开发出将某些金属转化为其他金属的方法。商人们的想法是利用炼金术士的技术将黄金转化为某种廉价金属，在越过边境并支付少量关税后，再将其转化回黄金。遗憾的是，炼金术士无法将任何金属转化为任意指定的其他金属。因此，从黄金获得某种特定金属的过程可能必须是一系列转化链，且每个阶段产生的金属都不同。炼金术士对他们的服务收取高额费用。对于他们能够进行的每种转化，他们都设定了将 1 kg 金属 $A$ 转化为金属 $B$ 的固定价格。商人们正在考虑应该以何种金属形式将黄金运过边境，以及应该采用什么样的炼金过程序列才能获得最高收益。

任务

帮助挽救 Byteotia 的经济！编写一个程序，完成以下工作：

• 读取所有金属的价格表以及炼金术士提供的转化价格。
• 确定一个金属序列 $m_0, m_1, \dots, m_k$，使得：
  • $m_0 = m_k$ 为黄金，
  • 对于每个 $i = 1, 2, \dots, k$，炼金术士能够从金属 $m_{i-1}$ 获得金属 $m_i$，并且
  • 执行整个炼金过程序列的成本（针对 1 kg 黄金），加上在边境支付的关税（$m_i$ 中价格最低的金属价格的 50%，其中 $i = 0, 1, \dots, k$），达到最小值。
• 我们假设在炼金过程中金属的重量不会改变。
• 输出所确定的炼金过程序列的成本加上边境关税的总和。

输入格式

标准输入的第一行包含一个正整数 $n$，表示不同金属的数量，$1 \le n \le 5\,000$。在第 $(k+1)$ 行（$1 \le k \le n$）中，有一个非负偶数 $p_k$：第 $k$ 种金属 1 kg 的价格，$0 \le p_k \le 10^9$。我们假设黄金的编号为 1。在第 $(n+2)$ 行中，有一个非负整数 $m$，等于炼金术士能够进行的转化过程数量，$0 \le m \le 100\,000$。在接下来的 $m$ 行中，每行包含三个由空格分隔的正整数，描述连续的转化过程。三元组 $a, b, c$ 表示炼金术士能够从第 $a$ 种金属获得第 $b$ 种金属，并且他们要求每转化 1 kg 材料支付 $c$ bytealers，$1 \le a, b \le n$，$0 \le c \le 10\,000$。有序对 $a$ 和 $b$ 在数据中最多出现一次。

输出格式

程序应向标准输出写入内容。第一行应包含一个整数，即程序确定的炼金过程成本加上边境关税的总和。

样例

输入 1

4
200
100
40
2
6
1 2 10
1 3 5
2 1 25
3 2 10
3 4 5
4 1 50

输出 1

60