Time Limit: 12000/6000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Senior Pan fails in his discrete math exam again. So he asks Master ZKC to give him graph theory problems everyday.

The task is simple : ZKC will give Pan a directed graph every time, and selects some nodes from that graph, you can calculate the minimum distance of every pair of nodes chosen in these nodes and now ZKC only cares about the minimum among them. That is still too hard for poor Pan, so he asks you for help.

The task is simple : ZKC will give Pan a directed graph every time, and selects some nodes from that graph, you can calculate the minimum distance of every pair of nodes chosen in these nodes and now ZKC only cares about the minimum among them. That is still too hard for poor Pan, so he asks you for help.

The first line contains one integer T, represents the number of Test Cases.1≤T≤5.Then T Test Cases, for each Test Cases, the first line contains two integers n,m representing the number of nodes and the number of edges.1≤n,m≤100000

Then m lines follow. Each line contains three integers $x_i,y_i$ representing an edge, and $v_i$ representing its length.1≤$x_i,y_i$≤n,1≤$v_i$≤100000

Then one line contains one integer K, the number of nodes that Master Dong selects out.1≤K≤n

The following line contains K unique integers $a_i$, the nodes that Master Dong selects out.1≤$a_i$≤n,$a_i$!=aj

Then m lines follow. Each line contains three integers $x_i,y_i$ representing an edge, and $v_i$ representing its length.1≤$x_i,y_i$≤n,1≤$v_i$≤100000

Then one line contains one integer K, the number of nodes that Master Dong selects out.1≤K≤n

The following line contains K unique integers $a_i$, the nodes that Master Dong selects out.1≤$a_i$≤n,$a_i$!=aj

提交代码