U86523 泳池（skylines）

小$A$ 是个爱玩的女孩子。暑假终于到了，小$A$ 决定请她的朋友们来游泳，她打算先在她家的私人海滩外圈一块长方形的海域作为游泳场。然而大海里有着各种各样的危险，有些地方水太深，有些地方有带毒的水母出没。她想让圈出来的这一块海域都是安全的。

小$A$ 的城市里有$n$ 座工厂，编号分别为$1-n$。工厂间连有$n-1$ 条双向管道，形成一个无向连通图，其中每条管道都有一定的长度，连接在两座不同的工厂间。 每座工厂都装有废水处理设施，工厂$i$的蓄水量记为$c_i$。由于工厂规模有限，工厂产生的废水必须经由管道输送到.另一座工厂进行处理。工厂$u$ 将废水输送到工厂$v$ 处理时，所需的运输成本等于无向图中$u$,$v$ 间最短路径的长度，并且会产生 $c_u-c_v$ 的额外成本（可能为负）。总成本等于运输成本与额外成本的和。 为了降低污染，在接下来的$q$ 天内，每一天只有一座工厂会产生废水。你需要确定这座工厂将废水输送到哪一座工厂进行处理，可使得总成本最小。由于选择可能不唯一，你只需输出最小的总成本。

第一行一个正整数$n$。 第二行$n$个正整数$c_i$。 下接$n −1$ 行，每行三个正整数$u,v,w$，表示一条双向管道两端工厂的编号及长度。 第$n+2$ 行一个正整数$q$。 下接$q$ 行，每行一个正整数$x$，表示这一天进行生产的工厂的编号。

输出$q$ 行，每行一个整数，表示这一天总成本的最小值。

第1 天，工厂2 输送到工厂4 是一种最优方案，成本为3 + (−2) = 1。 第2 天，工厂5 输送到工厂2 是一种最优方案，成本为5 + 2 = 7。 第3 天，工厂3 输送到工厂2 是一种最优方案，成本为1 + (−1) = 0。 第4 天，工厂4 输送到工厂1 是一种最优方案，成本为1 + 2 = 3。