P0717

[Poi2003]Smugglers

[Poi2003]Smugglers

Byteotia 以丰富的金矿资源闻名于世，每年都有大量矿产在它与邻国 Bitland 之间进行交易。商人携带矿产通过边境时，需要缴纳矿产价格的 50%50\% 作为关税。

一些炼金术士发明了将某种金属转换为另一种金属的方法。因此，商人可以先将昂贵的金属转换为价格较低的金属，携带其通过边境，再将其转换回来。不过，每种转换都需要向炼金术士支付相应的费用。

现在，一名商人希望将 1 kg1\text{ kg} 金子带过边境。请计算他需要支付的最小总费用。

输入格式

第一行包含一个整数 nn，表示金属的种类数。

接下来 nn 行，每行包含一个整数。第 k+1k+1 行的整数 pkp_k 表示第 kk 种金属每 1 kg1\text{ kg} 的价格。金子的编号为 11。

接下来一行包含一个整数 mm，表示转换方式的数量。

接下来 mm 行，每行包含三个整数 a,b,ca,b,c，表示将 1 kg1\text{ kg} 的第 aa 种金属转换为 1 kg1\text{ kg} 的第 bb 种金属需要支付费用 cc。

对于每个特定的有序金属对 (a,b)(a,b)，输入中至多出现一种对应的转换方式。

输出格式

输出一行，包含一个整数，表示将 1 kg1\text{ kg} 金子带过边境所需的最小总费用。

样例输入

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

数据范围

  • 1≤n≤50001\le n\le 5000；
  • 0≤pk≤1090\le p_k\le 10^9；
  • 0≤m≤1050\le m\le 10^5；
  • 1≤a,b≤n1\le a,b\le n；
  • 0≤c≤1040\le c\le 10^4；
  • 对于每个有序金属对 (a,b)(a,b)，至多存在一种转换方式。

来源与许可

本题为 POI 2003 试题「Smugglers」，题面与测试数据整理自 BZOJ 2607。

样例 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

输出

60