#OJ1799. Time Limit: 3 Sec Memory Limit: 128 MB
Time Limit: 3 Sec Memory Limit: 128 MB
Time Limit: 3 Sec Memory Limit: 128 MB
Description
A国是一个拥有n个城市的大国,B国正密谋对A国发动恐怖袭击,但在此之前需要打探A国的一些情报。于是B国的首脑派遣了s个恐怖分子潜入A国的不同城市,在此之前,B国已经在A国的t个不同的城市设立了情报交换站,用以将情报秘密送往本国。现已知该s个恐怖分子共享情报,他们想用最短的时间将情报送往t个交换站中的任意一个。你能帮他们计算所要走的最短路程吗?
Input
输入包含多组样例,每组样例首先包含四个正整数,城市的数量n(0<n<1000),城市中无向道路的条数m(0<m<1000000),恐怖分子的数量s(0<s<10),情报交换站的数量t(0<t<10),接下来会有m行,每行三个正整数,前两个为城市的标号u、v(1<=u,v<=n && u != v),第三个为他们之间的距离d(0<d<100)。相邻两城市之间可能有多条道路。接下来一行有s个正整数,代表当前恐怖分子所藏匿的城市标号,紧接着一行有t个正整数,代表情报交换站所在的城市标号。注意在s和t中出现的城市标号不重叠。输入以0 0 0 0结束。
Output
如果恐怖分子可以将情报送出,输出要走的最短路程。否则,输出"What a pity!"(不包含引号)。
Sample Input
6 1 3 3
4 5 1
1 2 3
4 5 6
6 2 2 4
1 3 3
2 4 4
1 2
3 4 5 6
0 0 0 0
Sample Output
What a pity!
3