很多游戏都有打怪升级的环节，玩家需要打败一系列怪兽去赢取成就和徽章。这里我们考虑一种简单的打怪升级游戏，游戏规则是，给定有 N 个堡垒的地图，堡垒之间有道路相连，每条道路上有一只怪兽把守。怪兽本身有能量，手里的武器有价值。打败怪兽需要的能量等于怪兽本身的能量，而怪兽一旦被打败，武器就归玩家所有 —— 当然缴获的武器价值越高，玩家就越开心。

你的任务有两件：

输入第一行给出两个正整数 N (≤1000) 和 M，其中 N 是堡垒总数，M 是怪兽总数。为简单起见，我们将堡垒从 1 到 N 编号。随后 M 行，第 i 行给出了第 i 只怪兽的信息，格式如下：

其中 B1 和 B2 是怪兽把守的道路两端的堡垒编号。题目保证每对堡垒之间只有一只怪兽把守，并且 怪兽能量 和 武器价值 都是不超过 100 的正整数。

再后面是一个正整数 K（≤N）和玩家想要攻克的 K 个目标堡垒的编号。

首先在一行中输出玩家空降的堡垒编号 B0。如果有多种可能，则输出编号最小的那个。

随后依次为玩家想要攻克的每个堡垒 B 推荐最省能量的攻克路径，并列出需要耗费的能量值和沿途缴获武器的总价值。注意如果最省力的路径不唯一，则选择沿途缴获武器总价值最高的解。格式为：

思路：枚举每个点s，以s为起点跑最短路，暴力求出最合理的空降位置（Floyd）。以空降位置再跑一遍最短路，维护出双关键字最短路径和路径信息，最后按题意输出路径即可。这一步的具体做法参考城市救援。

时间复杂度O(n^3)。