Problem Description

Big Center Forward is playing in an amusement park. There are $n$ attractions in the park, connected by a total of $m$ roads. Traveling along each road takes a certain amount of time. For the convenience of visitors, each attraction has a snack shop next to it: some shops sell cola, and the others sell hamburgers.

Because Big Center Forward loves eating, every time he arrives at an attraction, he will first buy either a cup of cola or a hamburger and consume it. However, if the number of hamburgers he has eaten exceeds the number of colas he has drunk by more than $k$, he will feel very thirsty; if the number of colas he has drunk exceeds the number of hamburgers he has eaten by more than $k$, he will feel very hungry.

Now Big Center Forward is at attraction $a$ and wants to go to attraction $b$, but he does not want to feel very thirsty or very hungry during the trip. He wants to know the minimum total time spent on the way. Since Big Center Forward is very lazy and does not want to think about it, can you help him solve this problem?

Note: Big Center Forward is extremely greedy, so the first thing he does upon arriving at each node is to eat (or drink), and only then consider other things. Therefore, he will buy a hamburger (or cola) at both the starting point and the ending point as well. You also need to ensure that at these two nodes he will not feel very hungry or very thirsty.

Input Format

The first line contains an integer $T$, indicating the number of test cases. For each test case, the format is as follows.

The first line contains three integers $n$, $m$, and $k$, representing the number of attractions, the number of roads, and the given parameter $k$ as described in the statement.

The second line contains $n$ integers. The $i$-th integer $a_i$ indicates the item sold by the shop next to attraction $i$: $1$ means cola, and $2$ means hamburger.

Lines $3$ to $(m + 2)$ each contain three integers $u, v, w$, indicating that there is an undirected road between attraction $u$ and attraction $v$, and traveling along this road takes time $w$.

Line $m + 3$ contains two integers $s, t$, indicating that Big Center Forward wants to travel from attraction $s$ to attraction $t$.

Output Format

For each test case, output one line containing one integer, the answer. If there is no feasible solution, output $-1$.

1
2 1 1
1 1
1 2 1
1 2

-1

1
2 1 2
1 1
1 2 1
1 2

1

Hint

Constraints

• For $30\%$ of the testdata, $n\leq 50, m\leq 1000$.
• For $100\%$ of the testdata, $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 testdata, $1 \leq T \leq 10$, and in each test point, the number of large testdata cases does not exceed $2$.

Additional Notes

• The path is not necessarily a simple path.
• Big Center Forward may pass through a node multiple times, and each time he will obtain a hamburger/cola.

Translated by ChatGPT 5