SP10447 CONTCITY - Contaminated City

在一个偏远的国家，有一座城市正面临一场前所未有的危机。致命的气体笼罩着城市，夺去了很多人的生命，但在城市的各个地方还有一些幸存者。幸存者所在的地方之间有一些道路相连，并且可以安全通行。这些道路是双向的，并且已知通过每条道路所需的天数，以及它们所连接的地方。每个地方有多少幸存者也是已知的。每位幸存者可以通过通行这些道路到达其他地方。 市长决定派遣多架直升机去救援这些幸存者。每架直升机都有一定的承载容量，即能救助的最大人数。每架直升机将在指定的地点和日期降落。你需要回答市长一个重要的问题：需要多少天才能救援所有幸存者？如果无法救援所有人，则需要回答最多能救援多少人。

第一行是测试用例的数量 $T$（$T \leq 40$）。 每个测试用例的第一行包括三个整数 $N$、$M$ 和 $H$，分别表示地点的数量、地方之间道路的数量以及将要派遣的直升机数量。每个地点由一个从 $1$ 到 $N$ 的编号唯一标识。接下来的 $N$ 行中，每行给出一个整数 $X_i$，表示在第 $i$ 个地方的幸存者数量。接下来的 $M$ 行中，每行包含三个整数 $A_j$、$B_j$ 和 $D_j$，表示存在一条连接地方 $A_j$ 和 $B_j$ 的道路，需 $D_j$ 天才能走完。可能有多条道路连接相同的地点对。接下来的 $H$ 行中，每行包含三个整数 $D_h$、$P_h$ 和 $C_h$，表示在第 $D_h$ 天，一架容量为 $C_h$ 的直升机会降落在地点 $P_h$。幸存者的总人数不超过 200。如果一个幸存者能通过一系列道路到达直升机所在地点，所需的总时间不会超过 1000 天。

对于每个测试用例，输出一行。如果所有人都可以被成功救援，输出 `All people can be rescued in D day(s).`，其中 $D$ 表示救援完所有人所需的最少天数。如果无法救援所有人，输出 `X survivor(s) can be rescued.`，其中 $X$ 是能救援的最多幸存者数量。 **本翻译由 AI 自动生成**