商店里有 nnn 件商品需要促销，每件商品的原价是 cic_ici 。现在有 mmm 种正在进行的促销，每种促销可以被表示为 aia_iai，bib_ibi，did_idi，表示当 aia_iai 商品被购买时，可以以价格 did_idi 购买 bib_ibi 商品，或当 bib_ibi 商品被购买时，可以以价格 did_idi 购买 aia_iai 商品。问购买所有促销商品需要花费最少的钱是多少。
第一行两个正整数 nnn , mmm ， 含义如题所述。
接下来一行 nnn 个正整数 cic_ici，表示商品的原价。
接下来 mmm 行，每行三个正整数 aia_iai ，bib_ibi ，did_idi，表示促销关系。
一行一个正整数 ansansans ，表示最少花费。
5 3 2 4 3 5 6 1 2 2 1 3 1 1 4 7
16
n≤106,m≤106,ci≤103,di≤103n \leq 10^6, m \leq 10^6, c_i \leq 10^3, d_i \leq 10^3n≤106,m≤106,ci≤103,di≤103