题目描述

大中锋正在一个游乐场里玩耍。游乐场里有 $n$ 个娱乐设施，娱乐设施之间相互有共 $m$ 条道路相连，经过每一条路都需要花费一定的时间。为了方便游客，每一个娱乐设施旁都会配有一个小卖部，一部分小卖部会销售可乐，另一部分会销售汉堡。

由于大中锋十分贪吃，所以每当他走到一个娱乐设施，他都会先去购买一杯可乐或一个汉堡，并把它们吃掉。但如果大中锋吃掉的汉堡数量比他喝掉的可乐数量多于 $k$ ，那他就会感到很渴；如果喝掉的可乐数量比吃掉的汉堡数量多于 $k$ ，那他就会感到很饿。

现在大中锋正在第 $a$ 个娱乐设施，他想前往第 $b$ 个娱乐设施，但在他前进的路途中他不希望自己很渴或很饿。大中锋想知道自己在路上少花费多少时间。但由于大中锋很懒惰，他不想思考这个问题。你能帮助他解决这个问题吗？

注意：大中锋非常贪吃，所以他到达每个点的第一件事是去吃(或者喝)，才考虑其他的事情，所以在起始点和终点他都会去买汉堡(可乐)，你也需要保证在这两个点他不会感到很饿或者很渴。

输入格式

输入的第一行是一个整数 $T$ 表示数据组数数，对于每组数据的格式如下：

第一行有三个整数，分别代表游乐场的娱乐设施个数 $n$，游乐场的道路数 $m$ ， 以及给出的参数 $k$，其含义见【题目描述】。

第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表编号为 $i$ 的娱乐设施旁的小卖部销售的物品，$1$ 表示可乐，$2$ 表示汉堡。

第 $3$ 到第 $(m + 2)$ 行，每行三个整数 $u, v, w$，代表从第 $u$ 个娱乐设施到第 $v$ 个娱乐设施有存在一条双向道路，通过该道路需要花费时间 $w$。

第 $m + 3$ 行有两个整数 $s, t$ ，代表大中锋想从娱乐设施 $s$ 前往娱乐设施 $t$。

输出格式

对于每组数据输出一行一个整数表示答案。如果无解，请输出 $-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

提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n\leq 50,m\leq 1000$。
• 对于 $100\%$ 的数据，保证 $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$。

对于所有数据，保证 $1 \leq T \leq 10$ ，且每个测试点的大数据不超过 $2$ 个。

题目补充说明

• 路径不一定是简单路径。
• 大中锋可以多次经过一个节点，同时每次都会取得汉堡/可乐。