UVA1247 Interstar Transport

[PDF](https://uva.onlinejudge.org/external/12/p1247.pdf) 在2100年，星际旅行将在银河系成为现实。星际交通运输局规划了一些往返于银河系各大热门星球间的星际航班，这些航班的花费（用银河币支付）已经提前确定好了，并翻译成了多种语言发布。对于不在航班路线里的星球，可以从最近的包含在航线内的星球乘坐较慢但是免费的星际巴士到达目的地。为了帮助游客们规划自己的旅行计划，星际交通运输局打算推出一款可以基于花费计算出最好路线的手机app。 给定旅行路线的起点和终点，请找出总花费最小的一条路线，并输出该路线沿途的所有星球。对于拥有相同花费的两条路线，输出途径星球数目最少的一条。 输入数据保证存在唯一解。

输入数据遵循以下规范： - 星际航班覆盖的总星球个数记为 $s$，满足 $1 \le s \le 26$，星球名称用英文大写字母（`A`，`B`，`C` 等）表示。 - 星际航班的总路线数记为 $p$，满足 $1 \le p \le 200$，且每两个星球间最多有一条路线。 - 任何路线的花费都小于等于 $100$ 银河币。 输入数据共 $p+n+2$ 行。 第一行，两个整数 $s$ 和 $p$，以一个空格分隔。 接下来 $p$ 行，两个英文大写字母 $e_i$，$e_j$ 和一个自然数 $d_{ij}$，表示 $e_i$ 和 $e_j$ 间有一条花费为 $d_{ij}$ 的路线。均以一个空格分隔。 下一行，一个整数 $n$，表示总询问次数。 接下来 $n$ 行，两个英文大写字母 $e_k$ 和 $e_m$，表示一位用户正查询从 $e_k$ 到 $e_m$ 的最优路线。以一个空格分隔。

输出数据共 $n$ 行。 对于每一行，请输出此次查询得到的最优路线途径的**所有**星球（包含起点和终点）。每两个星球间用一个空格分隔。 ## 输入输出样例 ### 输入 #1 ``` 5 7 A B 1 B C 2 C D 3 D E 2 E A 1 A D 3 A C 4 3 B D A D E C ``` ### 输出 #1 ``` B A D A D E A B C ``` ## 数据规模和约定 对于 $100\%$ 的数据，满足 $1 \le s \le 26$，$1 \le p \le 200$，$0 \le d_{ij} \le 100$，$n \le 20$。