SP8324 MILPATR - Military patrol

在一个反乌托邦世界中，有 $N$ 个城市，这些城市通过若干条单向道路相连。由于最近频繁发生抗议活动，政府计划使用军用巡逻车来镇压反抗。每辆巡逻车会被分配一组城市，以形成一个巡逻路线：如果分配给巡逻车的城市顺序是 $c_1, c_2, \ldots, c_k$，那么巡逻车会从城市 $c_1$ 出发，经由单向路前往 $c_2$，再从 $c_2$ 到 $c_3$，如此循环往复，直至从 $c_k$ 返回到 $c_1$。这种巡逻每天都会进行，以让抗议者一直感到恐惧。 需要注意以下几点： - 每个城市必须准确地出现在某辆巡逻车的序列中，并且只能出现一次。 - 每辆巡逻车必须进行移动，即必须被分配给多于一个城市。 政府在可用巡逻车的数量上没有限制。然而，他们希望尽量减少巡逻的总开支，因此要最小化巡逻车行驶的总距离。 给定反乌托邦的道路网络，计算巡逻车行驶的最小总距离，使所有城市都得到巡逻。若在给定条件下无法完成全国范围的巡逻任务，请注明。

第一行包含整数 $T$，表示测试用例的数量（$T \leq 10$）。 接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $R$，分别表示城市的数量和单向道路的数量（$N \leq 200, R \leq 10000$）。城市的编号为 $1, 2, 3, \ldots, N$。接下来 $R$ 行中，每行由三个整数 $N_1, N_2, D$ 表示一条单向道路，其中 $N_1$ 是起点城市，$N_2$ 是终点城市，$D$ 是道路的长度（$N_1 \neq N_2, 1 \leq D \leq 1000000$）。保证从任一城市 $N_1$ 到 $N_2$ 不会出现多于一条的单向道路。

对于每个测试用例，输出一行。如果巡逻可以完成，则输出巡逻车辆需要行驶的最小总距离；如果不能完成巡逻，则输出 `Impossible`。 **本翻译由 AI 自动生成**