TonyY是一个喜欢到处浪的男人，他的梦想是带着兰兰姐姐浪遍天朝的各个角落，不过在此之前，他需要做好规划。

现在他的手上有一份天朝地图，上面有n个城市，m条交通路径，每条交通路径都是单行道。他已经预先规划好了一些点作为旅游的起点和终点，他想选择其中一个起点和一个终点，并找出从起点到终点的一条路线亲身体验浪的过程。但是他时间有限，所以想选择耗时最小的，你能告诉他最小的耗时是多少吗？

Input

包含多组测试数据。

输入第一行包括两个整数n和m，表示有n个地点，m条可行路径。点的编号为1 - n。

接下来m行每行包括三个整数i, j, cost，表示从地点i到地点j需要耗时cost。

接下来一行第一个数为S，表示可能的起点数，之后S个数，表示可能的起点。

接下来一行第一个数为E，表示可能的终点数，之后E个数，表示可能的终点。

0<S, E≤n≤100000，0<m≤100000，0<cost≤100。

Output

输出他需要的最短耗时。

Sample Input

4 41 3 11 4 22 3 32 4 42 1 22 3 4

Sample Output

1

多源最短路，新建一个节点root，把root向每个起点连一条边权为0的边，跑最短路，最后答案为root到每个终点的最短路的最小值

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int h[100100],to[300100],nxt[300100],cost[300100],k=0;int d[100100];typedef pair
         
           P;priority_queue
          
           
,greater
           
 >q;void ins(int u,int v,int c){nxt[++k]=h[u];h[u]=k;to[k]=v;cost[k]=c;}void dij(int S){ memset(d,63,sizeof(d));d[S]=0; q.push(P(d[S],S)); while(!q.empty()) { P p=q.top();q.pop();int u=p.second; if(d[u]