Pitney Bowes is modeling a solution for ABC company for their logistics team which will aim at reducing delivery time for ABC company and creating excellent experience for their customers.
Consider, there are total N cities that the company’s logistics team travels, also called as vertices in technical terms. These cities are connected by a total of M roads also called as edges. Each edge has a non-negative integer weight.
Now, out of these N cities P of the cities have erratic traffic pattern. Let us call such cities Cursed Cities.You have been provided the list of P Cursed Cities. You Now, you need to help the logistics team find a path from city A to city B such that we visit minimum possible number of Cursed Cities while travelling along this path.
It there are multiple paths satisfying the above requirement, you need to find the path with minimum sum of weights of the edges it contains. If there exists no path that originates at city A and visits ≤L cursed cities, ending at city B, print −1 instead.
Can you do it ?
Input Format:
First line consists of a single integer T denoting the number of test cases.
First line of each test case consists of six space separated integers denoting N, P, L, M, A and B.
Second line of each test case consists P space separated integers denoting the cursed vertices.
Each of following M lines in every test case consists of three space-separated integers U, V and W, denoting that there is an undirected edge between vertices U and V having weight W.
Output Format:
For each test case, if all the paths from vertex A to B visits more than L cursed vertices print 1. Otherwise print two space separated integers, the minimum number of cursed vertices visited, and the length of the path. If there are multiple paths which visits minimum number of cursed vertices then pick the one having smallest length.
Input Constraints:
1≤T≤100
2≤N≤2×105
1≤P≤N
0≤L≤2×105
1≤M≤2×105
0≤A,B≤N−1
There always exists at least one path from A to B in the city.
0≤Pi≤N−1
0≤U,V≤N−1
1≤W≤109
