题目描述

Byteotia 因为它丰富的金矿资源而闻名世界。所以在和它的邻国 Bitland 的边界上每年都有大量的金矿交易。不幸的是由于税务的繁重，商人带着矿产穿边境时都要交纳矿产价格的 $50\%$ 作为关税。

但是幸运的是，有一些炼金术士已经发明了一些能把某一种矿产转化成另一种的方法。于是这样在交易时就可以先把昂贵的矿产转化成便宜的，等到带过边境以后在转换回来。但是由于这项工作费时费力，炼金术士对于每种转换都要收取相应的费用。现在有个商人想将 $1kg$ 金子带过边境，他想知道最少的花费是多少。

输入格式

第一行仅一个数 $n$ 表示有多少种金属矿产。

接下来 $n$ 行表示每种金属 $1kg$ 的单价。

第 $k+1$ 行的数 $p_k$ 为第 $k$ 种金属的单价。

我们假设金子的标号为 $1$。接下来一个正数 $m$ 表示一共有 $m$ 种转换方式。

接下来 $m$ 行每行描述一个转换，它由三个数 $a,b,c$ 表示把 $1kg$ 的 $a$ 金属转换为 $1kg$ 的 $b$ 金属需要 $c$ 的代价。

输出格式

输出一行，表示把 $1kg$ 的金子带过边境的最小花费。

样例输入

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

样例输出

60

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 5000$，$0 \le p_k \le 10^9$，$0\le m \le 100000$，$1 \le a,b \le n, 0 \le c \le 10000$。

同时数据保证对于特定的金属对 $a$ 和 $b$ 最多只会出现一次。