SP29454 MARSCOL - Martian Colony

《火星殖民地》是一款著名公司开发的单人策略游戏，玩家需要在游戏中摧毁位于火星上的多个殖民地。 火星上共有 **N** 个村庄，标号从 **1** 到 **N**。每个标号为 **i** 的村庄拥有 **di** 数量的钻石。村庄之间有 **E** 条单向道路，即只可以从村庄 **u** 到达村庄 **v**。当一组村庄中每对村庄 **u** 与 **v** 都存在路径相连，而且这种连通性是双向时，这组村庄构成一个殖民地。这里的路径指由多条连续道路构成的行进路线。每个殖民地的“生命值”是其内部所有道路长度之和。摧毁一个殖民地需要消耗等于其生命值的火星点数，摧毁后，该殖民地内所有村庄的钻石总数会加到玩家的分数中。 阿隆是你的挚友，他热衷于策略游戏，目前正在挑战这款新游戏。他希望能尽可能获得最高分。在游戏的一个阶段，他手头有 **M** 点火星点数。他想知道，如何在不超过 **M** 点火星点数的条件下，取得最大的得分。作为他的好朋友，你需要帮他精确地计算这个最大得分。

第一行输入一个整数 **T**，表示测试用例的数量。每个测试用例之前都会有一个空行。每个测试用例的第一行包含三个整数 **N, E** 和 **M (1 ≤ N, E, M ≤ 10^5)**。接下来的一行包含 **N** 个整数 **di (-100 ≤ di ≤ 100)**，表示第 **i** 个村庄的钻石数量。接下来的 **E** 行，每行包含三个整数 **u, v** 和 **w (1 ≤ u, v ≤ N, 1 ≤ w ≤ 100)**，表示从村庄 **u** 到村庄 **v** 有一条长度为 **w** 的道路。

对于每个测试用例，请输出一行，格式为 `“Case X: S”`，其中 **X** 是测试用例编号（从 1 开始），**S** 是阿隆可以获得的最大得分。

- $1 \le T \le 10$ - $1 \le N, E, M \le 10^5$ - $-100 \le d_i \le 100$ - $1 \le u, v \le N$ - $1 \le w \le 100$ **本翻译由 AI 自动生成**