SP151 COURIER - The Courier

Byteland 是一个人烟稀少的国家，不同城市的居民之间几乎没有交流。这里没有定期的邮政服务，大部分时间由一个快递员就能满足所有货物运输需求。然而，在圣诞节这一天，快递员的工作量要比平时大不少。由于他每次只能用自行车运送一个包裹，所以不得不在城市之间来回奔波。 快递员需要设计一条路线，从他的家乡出发，按照任意顺序完成所有运送任务（即从发件城市到达收件城市，每次只能携带一个包裹），最后返回到家乡。所有道路都是双向的，尽管并不是所有城市之间都有直接的道路连接，并且某些城市之间可能有多条道路连接。给定所有道路的长度和需要完成的任务，请你计算出快递员骑行的最短路线长度。

输入首先是一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例。 每个测试用例的第一行包含三个整数：$n$（城市数量）、$m$（道路数量）和 $b$（快递员的家乡编号）。（$1 \leq n \leq 100$，$1 \leq b \leq m \leq 10000$）。接下来的 $m$ 行中，每行包含三个整数 $u_i$、$v_i$ 和 $d_i$，表示城市 $u_i$ 和 $v_i$ 之间有一段长度为 $d_i$ 的道路（$1 \leq u_i, v_i \leq 100$，$1 \leq d_i \leq 10000$）。接下来的一行包含一个整数 $z$，表示待处理的运输请求数（$1 \leq z \leq 5$）。接下来的 $z$ 行，每行分别包含三个整数 $u_j$、$v_j$ 和 $b_j$，表示需要将 $b_j$ 个包裹从城市 $u_j$ 运送到城市 $v_j$。所有 $b_j$ 的和不超过 12。

对于每个测试用例，输出一个整数，表示完成所有运输任务所需的最短骑行路线长度。 **本翻译由 AI 自动生成**