{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"众所周知,TT 有一只魔法猫。\n\n今天他在 B 站上开启了一次旅行直播,记录他与魔法猫在喵星旅游时的奇遇。 TT 从家里出发,准备乘坐猫猫快线前往喵星机场。猫猫快线分为经济线和商业线两种,它们的速度与价钱都不同。当然啦,商业线要比经济线贵,TT 平常只能坐经济线,但是今天 TT 的魔法猫变出了一张商业线车票,可以坐一站商业线。假设 TT 换乘的时间忽略不计,请你帮 TT 找到一条去喵星机场最快的线路,不然就要误机了!"}},{"title":"输入","value":{"format":"MD","content":"输入包含多组数据。每组数据第一行为 3 个整数 N, S 和 E (2 ≤ N ≤ 500, 1 ≤ S, E ≤ 100),即猫猫快线中的车站总数,起点和终点(即喵星机场所在站)编号。\n\n下一行包含一个整数 M (1 ≤ M ≤ 1000),即经济线的路段条数。\n\n接下来有 M 行,每行 3 个整数 X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100),表示 TT 可以乘坐经济线在车站 X 和车站 Y 之间往返,其中单程需要 Z 分钟。\n\n下一行为商业线的路段条数 K (1 ≤ K ≤ 1000)。\n\n接下来 K 行是商业线路段的描述,格式同经济线。\n\n所有路段都是双向的,但有可能必须使用商业车票才能到达机场。保证最优解唯一。"}},{"title":"输出","value":{"format":"MD","content":"对于每组数据,输出3行。第一行按访问顺序给出 TT 经过的各个车站(包括起点和终点),第二行是 TT 换乘商业线的车站编号(如果没有使用商业线车票,输出\"Ticket Not Used\",不含引号),第三行是 TT 前往喵星机场花费的总时间。\n\n**本题不忽略多余的空格和制表符,且每一组答案间要输出一个换行**"}},{"title":"输入样例","value":{"format":"MD","content":"4 1 4\n4\n1 2 2\n1 3 3\n2 4 4\n3 4 5\n1\n2 4 3"}},{"title":"输出样例","value":{"format":"MD","content":"1 2 4\n2\n5\n"}}]}