UVA11374 Airport Express

在$Iokh$市中，机场快线是市民从市内去机场的首选交通工具。机场快线分为经济线和商业线两种，线路、速度和价钱都不同。你有一张商业线车票，可以坐一站商业线，而其他时候只能乘坐经济线。假设换乘时间忽略不计，你的任务是找一条去机场最快的线路。

输入包含多组数据。每组数据第一行为$3$个整数$N, S$和$E(2 \leq N \leq 500, 1 \leq S, E \leq 100)$，即机场快线中的车站总数，起点和终点（即机场所在站）编号。下一行包含一个整数$M(1 \leq M \leq 1000)$，即经济线的路段条数。以下$M$行每行3个整数$X, Y, Z(1 \leq X, Y \leq N, 1 \leq Z \leq 100)$，表示可以乘坐经济线在车站$X$和车站$Y$之间往返，其中单程需要$Z$分钟。下一行为商业线的路段条数$K(1 \leq K \leq 1000)$，以下$K$行是这些路段的描述，格式同经济线。所有路段都是双向的，但有可能必须使用商业车票才能到达机场。保证最优解唯一。

对于每组数据，输出$3$行。第一行按访问顺序给出经过的各个车站（包括起点和终点），第二行是换乘商业线的车站编号（如果没有商业线车票，输出`Ticket Not Used`），第三行是总时间。 **注意**：输出时，每两组数据之间要加一个空行。并且不会过滤行末空格。 Translated by @andyli