SP26893 PRISTOJBA - Pristojba

在一个遥远的星系中，一家新兴的低成本太空航空公司开始提供每日的星际航班服务。 星系中总共有 **N** 个星球，每个星球用 1 到 **N** 的整数编号。两个星球之间的航班费用只由这两个星球的起降费用决定。对于每个编号为 **k** 的星球，其费用为 **p $ _{k} $**，因此星球 **a** 到星球 **b** 的航班费用为 **p $ _{a} $ + p $ _{b} $**。 太空航空公司希望确定每日的航班安排，使得所有星球都能够彼此直接或间接到达。 由于宇宙空间的限制，航班只能在某些特定的星球对之间运行。允许的航班由 **M** 条许可规则描述，格式为“**x $ _{k} $ a $ _{k} $ b $ _{k} $**”，表示可以在星球 **x $ _{k} $** 和任何编号在 **a $ _{k} $** 到 **b $ _{k} $** 之间的星球 **c** 之间进行双向航班。 请找出所有星球连通所需的最小总航班费用。

第一行包含两个整数 **N** 和 **M**，分别表示星球的数量和许可航班的数量。 第二行包含 **N** 个整数 **p $ _{1} $, p $ _{2} $, ..., p $ _{N} $**，分别表示每个星球的费用。 接下来的 **M** 行，每行包含三个整数 **x $ _{k} $, a $ _{k} $, b $ _{k} $**，描述允许的航班。

输出一个整数，代表使所有星球连通所需的最小总航班费用。

- 对于每个 **p $ _{k} $**，有 $0 \leq p $ _{k} $ \leq 10^5$。 - 每条许可规则满足 **x $ _{k} $ < a $ _{k} $** 或 **x $ _{k} $ > b $ _{k} $**。 - 可能有些星球对会在多条许可规则中出现。 - 始终可以通过选择合适的航班使所有星球连通。 **本翻译由 AI 自动生成**