Problem Description

Da Zhongfeng is playing in an amusement park. The park has $n$ entertainment facilities, interconnected by $m$ roads. Each road requires a certain amount of time to traverse. For the convenience of visitors, each facility has a small shop, some of which sell cola and others sell hamburgers.

Since Da Zhongfeng is very greedy for food, whenever he arrives at a facility, he will first buy and consume a cup of cola or a hamburger. However, if the number of hamburgers he eats exceeds the number of colas he drinks by more than $k$, he will feel very thirsty; if the number of colas he drinks exceeds the number of hamburgers he eats by more than $k$, he will feel very hungry.

Currently, Da Zhongfeng is at the $a$-th facility and wants to go to the $b$-th facility. However, he does not want to feel very thirsty or very hungry along the way. Da Zhongfeng wants to know how much time he can save on his journey. But since he is very lazy, he doesn't want to think about this problem. Can you help him solve this problem?

Note: Da Zhongfeng is extremely greedy for food, so his first action upon reaching each facility is to eat (or drink), before considering anything else. Therefore, at both the starting and ending points, he will buy a hamburger (or cola), and you also need to ensure that he does not feel very hungry or very thirsty at these points.

Input Format

The first line of input is an integer $T$ representing the number of test cases. Each test case is formatted as follows:

The first line contains three integers: the number of facilities $n$, the number of roads $m$, and the parameter $k$, as described in the problem statement.

The second line contains $n$ integers, where the $i$-th integer $a_i$ represents the item sold at the shop next to the $i$-th facility, with $1$ indicating cola and $2$ indicating a hamburger.

From the third to the $(m + 2)$-th line, each line contains three integers $u, v, w$, representing a bidirectional road between the $u$-th and $v$-th facilities, which takes $w$ time to traverse.

The $(m + 3)$-th line contains two integers $s, t$, representing Da Zhongfeng's starting and destination facilities.

Output Format

For each test case, output a single integer representing the answer. If there is no solution, output $-1$.

Sample Input and Output

Input Sample #1

1
2 1 1
1 1
1 2 1
1 2

Output Sample #1

-1

Input Sample #2

1
2 1 2
1 1
1 2 1
1 2

Output Sample #2

1

Notes/Hints

Data Size and Constraints

• For $30\%$ of the data, $n \leq 50, m \leq 1000$.
• For $100\%$ of the data, $1 \leq n \leq 10000$, $1 \leq m \leq 100000$, $1 \leq k \leq 10$, $1 \leq a_i \leq 2$, $1 \leq u, v, s, t \leq n$, $1 \leq w \leq 10000$.

For all data, $1 \leq T \leq 10$, and no more than $2$ large test cases per test point.

Additional Notes

• The path does not necessarily have to be simple.
• Da Zhongfeng can pass through a node multiple times, and will always consume a hamburger/cola each time.

见题面 Input 部分

见题面 Output 部分