{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"在 Iokh 市中,机场快线是市民从市内去机场的首选交通工具。\n\n机场快线分为经济线和商业线两种,线路、速度和价钱都不同。\n\n你有一张商业线车票,可以坐一站商业线,而其他时候只能乘坐经济线。\n\n假设换乘时间忽略不计,你的任务是找一条去机场最快的线路。"}},{"title":"输入","value":{"format":"MD","content":"输入包含多组数据。\n\n每组数据第一行为 $3$ 个整数 $N, S,E(2\\le N\\le 500, 1 \\le S, E \\le 100)$,即机场快线中的车站总数,起点和终点(即机场所在站)编号。\n\n下一行包含一个整数 $M(1\\le M\\le1000)$,即经济线的路段条数。\n\n以下$M$行每行 $3$ 个整数 $X,Y,Z(1\\le X,Y\\le N,1\\le Z\\le 100)$,表示可以乘坐经济线在车站 $X$和车站 $Y$ 之间往返,其中单程需要 $Z$ 分钟。\n\n下一行为商业线的路段条数 $K(1\\le K\\le1000)$,以下 $K$ 行是这些路段的描述,格式同经济线。所有路段都是双向的,但有可能必须使用商业车票才能到达机场。\n\n保证最优解唯一。"}},{"title":"输出","value":{"format":"MD","content":"对于每组数据,输出 $3$ 行。\n\n第一行按访问顺序给出经过的各个车站(包括起点和终点),第二行是换乘商业线的车站编号(如果没有商业线车票,输出 `Ticket Not Used`),第三行是总时间。"}},{"title":"输入样例","value":{"format":"MD","content":"```plaintext\n4 1 4\n4\n1 2 2\n1 3 3\n2 4 4\n3 4 5\n1\n2 4 3\n```"}},{"title":"输出样例","value":{"format":"MD","content":"```plaintext\n1 2 4\n2\n5\n```"}}]}