1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<string>  5 #include<sstream>  6 #include<algorithm>  7 #include<cmath>  8 #include<set>  9 #include<map> 10 #include<stack> 11 #include<queue> 12 #include<deque> 13 #include<cstdlib> 14 #include<cctype> 15 #include<list> 16 #include<vector> 17 using namespace std; 18 const int INF = 0x7f7f7f7f; 19 const int MAXN = 1000 + 10; 20 struct Edge 21 { 22     int from_, to_, dist_; 23     Edge(int from = 0, int to = 0, int dist= 0):from_(from), to_(to), dist_(dist){} 24 }; 25 struct HeapNode 26 { 27     int d_, u_; 28     HeapNode(int d, int u):d_(d), u_(u){} 29     bool operator < (const HeapNode& rhs) const 30     { 31         return d_ > rhs.d_; 32     } 33 }; 34 struct Dijkstra 35 { 36     int n, m; 37     vector<Edge> edges; 38     vector<int> G[MAXN]; 39     bool done[MAXN]; 40     int d[MAXN]; 41     int p[MAXN]; 42     void init(int n) 43     { 44         this -> n = n; 45         for(int i = 0; i < n; ++i) 46             G[i].clear(); 47         edges.clear(); 48     } 49     void AddEdge(int from, int to, int dist) 50     { 51         edges.push_back(Edge(from, to, dist)); 52         m = edges.size(); 53         G[from].push_back(m - 1); 54     } 55     void dijkstra(int s) 56     { 57         priority_queue<HeapNode> Q; 58         for(int i = 0; i < n; ++i) 59             d[i] = INF; 60         d[s] = 0; 61         memset(done, 0, sizeof done); 62         Q.push(HeapNode(0, s)); 63         while(!Q.empty()) 64         { 65             HeapNode x = Q.top(); 66             Q.pop(); 67             int u = x.u_; 68             if(done[u]) continue; 69             done[u] = true; 70             for(int i = 0; i < G[u].size(); ++i) 71             { 72                 Edge& e = edges[G[u][i]]; 73                 if(d[e.to_] > d[u] + e.dist_) 74                 { 75                     d[e.to_] = d[u] + e.dist_; 76                     p[e.to_] = G[u][i]; 77                     Q.push(HeapNode(d[e.to_], e.to_)); 78                 } 79             } 80  81         } 82     } 83 }; 84 int a[15]; 85 int b[15]; 86 int main() 87 { 88     int n, m, s, t; 89     while(scanf("%d%d%d%d", &n, &m, &s, &t) == 4) 90     { 91         if(!n && !m && !s && !t) return 0; 92         memset(a, 0, sizeof a); 93         memset(b, 0, sizeof b); 94         Dijkstra dij; 95         dij.init(n); 96         while(m--) 97         { 98             int u, v, d; 99             scanf("%d%d%d", &u, &v, &d);100             dij.AddEdge(u - 1, v - 1, d);101             dij.AddEdge(v - 1, u - 1, d);102         }103         for(int i = 0; i < s; ++i)104             scanf("%d", &a[i]);105         for(int i = 0; i < t; ++i)106             scanf("%d", &b[i]);107         int ans = INF;108         for(int i = 0; i < s; ++i)109         {110             dij.dijkstra(a[i] - 1);111             for(int j = 0; j < t; ++j)112                 ans = min(ans, dij.d[b[j] - 1]);113         }114         if(ans == INF)115             printf("What a pity!\n");116         else printf("%d\n", ans);117     }118     return 0;119 }