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