Dazhongfeng is playing in an amusement park. The park has many entertainment facilities connected by roads, and traveling along each road takes a certain amount of time. To accommodate visitors, each facility has a small shop nearby; some shops sell cola, while others sell burgers.

Because Dazhongfeng is very gluttonous, every time he arrives at an entertainment facility, he will first buy a cup of cola or a burger and consume it. However, if the number of burgers Dazhongfeng has eaten exceeds the number of colas he has drunk by more than $k$, he will feel thirsty; if the number of colas he has drunk exceeds the number of burgers he has eaten by more than $k$, he will feel hungry.

Dazhongfeng is currently at the $a$-th entertainment facility and wants to go to the $b$-th entertainment facility, but he does not want to feel thirsty or hungry during his journey. Dazhongfeng wants to know the minimum time required to travel. Since Dazhongfeng is lazy, he does not want to think about this problem. Can you help him solve it?

Note: Dazhongfeng is very gluttonous, so the first thing he does upon arriving at any point is to eat (or drink) before considering anything else. Therefore, he will buy a burger (or cola) at both the starting point and the destination, and you must ensure that he does not feel hungry or thirsty at either of these two points.

Input

The input contains multiple test cases. The first line contains a positive integer $T$ representing the number of test cases.

For each test case: The first line contains three integers $n, m, k$, where $n$ is the total number of entertainment facilities in the park, $m$ is the total number of roads, and $k$ is as described in the problem. The next line contains $n$ integers, where the $i$-th integer represents what the $i$-th shop sells: $1$ for cola, $2$ for burgers. The next $m$ lines each contain three integers $p, q, t$, representing a road from the $p$-th facility to the $q$-th facility that takes $t$ units of time to traverse. The last line contains two integers $a, b$, representing that Dazhongfeng wants to travel from facility $a$ to facility $b$.

Output

For each test case, output a single integer $t$ representing the minimum time required to travel from facility $a$ to facility $b$ without feeling thirsty or hungry. If it is impossible to reach the destination, output $-1$.

Examples

Input 1

1
2 1 1
1 1
1 2 1
1 2

Output 1

-1

Input 2

1
2 1 2
1 1
1 2 1
1 2

Output 2

1

Constraints

For 30% of the data: $n \le 50, m \le 1000$ For 100% of the data: $n \le 10000, m \le 100000, k \le 10, t \le 10000$ For all data, it is guaranteed that $T \le 10$, and there are no more than 2 large test cases per input.