A171744.Yuilice 的小区接送

Yuilice 要为小区安排接送路线。小区有 $n$ 个站点和 $n-1$ 条双向道路，站点编号为 $1$ 到 $n$，道路构成一棵树。第 $i$ 个站点的端点服务费为 $p_i$，每条道路有非负的行驶费用。

你需要把全部站点划分为若干条简单路径，每个站点恰好属于一条路径，路径之间不能有公共站点。简单路径不会重复经过站点，单独一个站点也算一条路径。

每条路径的费用按以下方式计算：

• 支付一次固定派车费 $C$。
• 支付路径经过的每条道路的行驶费用。
• 若路径至少包含两个站点，支付两个端点各自的服务费，内部站点不收费。
• 若路径只有一个站点，只支付该站点一次服务费。

请计算所有路径费用之和的最小可能值。

第一行包含一个整数 $n$ 和一个整数 $C$。

第二行包含 $n$ 个整数 $p_1,\ldots,p_n$。

接下来 $n-1$ 行，每行包含三个整数 $u,v,w$，表示站点 $u,v$ 之间有一条行驶费用为 $w$ 的双向道路。保证这些道路构成一棵树。

输出一个整数，表示最小总费用。

样例解释

样例 $1$：将三个站点合成路径 $1\to2\to3$，费用为 $5+6+6+0+0=17$。若三个站点各自形成路线，费用为 $15+100=115$；若只合并一条道路，费用为 $10+6+100=116$。

样例 $2$：只有一条单站路线，费用为 $7+3=10$，服务费只计算一次。

数据范围

对于所有测试数据，满足 $1\le n\le2\times10^5$，$0\le C,p_i,w\le10^9$，$1\le u,v\le n$，$u\ne v$。道路无重边，图连通且无环。

特殊性质 S：存在一个站点与其余所有站点直接相邻；$n=1$ 时也视为满足此性质。

测试点	分值	额外限制
1–2	10	特殊性质 S
3–6	20	$n\le18$
7–20	70	无额外限制