SP5523 PHU09K - Highway Patrol

Megacity 的犯罪率正在上升。为了遏制犯罪，当局建立了一个高速巡逻队。这个城市由几条单向道路构成，每条道路的两端都有一个巡逻基地，每个基地有若干名巡逻员。起初，每个基地会派出一名巡逻员沿着从该基地出发的所有道路进行巡逻。巡逻员在道路上巡逻时，一旦到达道路另一端的基地，就会在那儿等待，并选择那些等候时间最长的巡逻员，派他们去巡逻等待时间最长的道路。 然而，他们遇到了难题，因为道路巡逻频率越来越依赖于基地间道路的出入口数量。如果一个基地出入口不平衡，即出发的道路多于抵达的道路，那么这些道路的巡逻频次会降低。如果某个基地没有任何道路到达，那么从该基地出发的道路将只被巡逻一次。在这样的情况下，巡逻队决定从计划中移除一些道路，以便每个基地的出入口道路数量能够平衡。剩下的道路将通过视频监控进行监管。但出于安全考量，某些道路必须被巡逻。 现在，给出巡逻和安装视频监控的费用，计算出监控整个城市的最低成本。请注意，视频监控不能完全取代巡逻，因此至少有一条道路必须进行巡逻。

输入的第一行为整数 $T$（测试用例数）。接下来是 $T$ 个测试用例。每个测试用例的第一行为两个整数 $N$ 和 $M$，分别表示基地数量和道路数量。接下来的 $M$ 行，每行包含三个整数 $u$、$v$ 和 $c$，表示有一条从基地 $u$ 到基地 $v$ 的道路，其巡逻费用为 $c$。随后一行包含一个整数 $K$，表示必须巡逻的道路数量。接下来的 $K$ 行，每行包含两个整数 $a$ 和 $b$，表示必须巡逻的道路连接基地 $a$ 和 $b$。最后一行包含一个整数 $V$，表示安装视频监控的费用。

对于每个测试用例，输出一行。首先输出测试用例编号，然后输出监控道路的最低成本。如果不能达到要求的条件，则输出「impossible」（不带引号）。

- $1 \le T \le 10$ - $1 \le N \le 100$ - $1 \le M \le 1000$ - $1 \le K \le M$ - $1 \le c, V \le 10^5$ **本翻译由 AI 自动生成**