测试数据来自 system/2239

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

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

【输入格式】

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

【输出格式】

　　对于每组数据，如果没有使用商业票，输出两行，第一行输出“Ticket Not Used”，第二行输出 \(S\) 到 \(E\) 的最短时间。如果使用了商业票，则输出一行，是 \(S\) 到 \(E\) 的总时间。

【输入输出样例】

　Input

4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3
7 2 5
6
7 1 3
4 2 3
5 2 9
3 6 8
7 3 5
6 4 4
5
5 2 8
3 3 9
1 2 8
5 5 8
3 4 1
7 2 3
7
6 1 9
1 7 8
3 2 4
2 4 6
6 3 6
5 4 4
6 5 2
4
7 6 5
3 4 10
2 5 7
6 7 5

　Output

5
8
Ticket Not Used
4

【数据限制】

　　对于 \(100\%\) 的数据， \(1≤N≤500\)，\(1≤M,K≤1000\)。

【来源】

　　Mr.he