Problem Description

Although Caoer is a road crazy (i.e. he has been in Hangzhou Electric Power for more than a year, and even lost his way in the campus, Khan ~), Caoer still likes to travel, because he will meet many people (prince charming, ^ 0 ^), many things, rich experience and beautiful scenery during the journey Cao'er wants to go to many places. She wants to go to the Tokyo Tower to see the night view, to Venice to see the movie, to Yangmingshan to see the taro, to New York to see the snow purely, to Paris to drink coffee and write letters, to Beijing to visit Meng Jiangnu Seeing that winter vacation is coming, we can't waste such a large period of time. We must give ourselves a good holiday, but we can't waste the training. So cao'er decided to go where he wanted to go in the shortest time! Because cao'er's home is in a small town, there is no train passing by, so she can only go to the neighboring city to take the train.

Input

There are multiple groups of input data. The first row of each group is three integers T, S and D, indicating that there are t roads, S in cities adjacent to Caoer'S home, and D in places where Caoer wants to go;

Then there are T lines, each line has three integers a,b, time, indicating that the distance between a and B cities is time hour; (1 = < a,b) < 1000; a,b There may be more than one road between)

There are S numbers in the next T+1 line, indicating the city connected with Caoer'S home;

The next T+2 line has D numbers, indicating that the grass wants to go to places.

Then there are T lines, each line has three integers a,b, time, indicating that the distance between a and B cities is time hour; (1 = < a,b) < 1000; a,b There may be more than one road between)

There are S numbers in the next T+1 line, indicating the city connected with Caoer'S home;

The next T+2 line has D numbers, indicating that the grass wants to go to places.

Output

The shortest time that grass can go to a favorite city.

Sample Input

6 2 3

1 3 5

1 4 7

2 8 12

3 8 4

4 9 12

9 10 2

1 2

8 9 10

Sample Output

9

#include<bits/stdc++.h> using namespace std; #define inf 99999999 int n,u,v,w,book[1005],dis[1005],e[1005][1005],minn; void dj() { int i,j; for(i=1;i<=n-1;i++) { minn=inf; for(j=1;j<=n;j++) { if(!book[j]&&dis[j]<minn) { minn=dis[j]; u=j; } } book[u]=1; for(v=1;v<=n;v++) { if(e[u][v]<inf&&dis[v]>dis[u]+e[u][v]) dis[v]=dis[u]+e[u][v]; } } } int main() { int i,j,k[1005],a,t,s,d; while(cin>>t>>s>>d) { n=0; memset(k,0,sizeof k); for(i=0;i<=1000;i++) for(j=0;j<=1000;j++) e[i][j]=inf; e[i][i]=0; while(t--) { scanf("%d%d%d",&u,&v,&w); n=max(n,max(u,v)); if(w<e[u][v]) e[u][v]=e[v][u]=w; } while(s--) { scanf("%d",&v); e[0][v]=e[v][0]=0; } memset(book,0,sizeof book); book[0]=1; for(i=0;i<=n;i++) dis[i]=e[0][i]; dj(); for(i=1;i<=d;i++) scanf("%d",&k[i]);

minn=inf; for(i=1;i<=d;i++) { if(minn>dis[k[i]]) minn=dis[k[i]]; } printf("%d\n",minn); } return 0; }