3742 年已经到来，现在轮到赛博乐园主办 APIO 了。在这个世界上有 $N$ 个国家，这些国家由 $0$ 到 $N − 1$ 标号，还有 $M$ 条双向道路（每条边双向都可以通行），这些道路由 $0$ 到 $M − 1$ 标号。每条道路连接两个不同的国家，$x[i]$ 和 $y[i]$，并需要花费时间 $c[i]$ 来通过该道路。除了你所在的国家的选手，所有选手都已经聚集在赛博乐园参加 APIO 了。你生活在国家 $0$，而赛博乐园是国家 $H$。你作为你的国家最聪明的人，你的帮助刻不容缓。更具体地，你需要确定从你的国家到达赛博乐园所需的最少时间。

在经过有些国家时，你可以清除你的当前总通过时间。此外，还有些国家在你经过他们时可以将你的当前总通过时间除以 $2$（我们称之为“除以 $2$ 的能力”）。你可以重复经过一个国家。每次你经过一个国家时，你可以选择是否使用这个国家的特殊能力。但你每次经过一个国家时最多可以使用一次特殊能力（如果你多次经过一个国家，你每次经过都可以使用至多一次该国家的特殊能力）。此外，为了防止被赛博乐园化学基金会抓住，你最多只能使用“除以 $2$ 的能力”$K$ 次。一旦你到达赛博乐园，你就不能移动到其他任何地方，因为伟大的 APIO 竞赛即将开赛了！

给出一个数组 $arr$ ，其中 $arr[i]$ 表示国家 $i (0 \le i \le N − 1)$ 的特殊能力。每个国家有下面 $3$ 种特殊能力之中的一种：

• $arr[i] = 0$，意思是这个国家可以让当前总通过时间为 $0$。
• $arr[i] = 1$，表示这个国家不会改变你的当前总通行时间。
• $arr[i] = 2$，表示这个国家拥有让当前总通行时间除以 $2$ 的能力。

保证 $arr[0] = arr[H] = 1$ 成立。换句话说，赛博乐园和你所在的国家没有任何特殊能力。

你的国家不希望错过 APIO 的任何时刻，所以你需要找到到达赛博乐园的最短时间。如果你不能到达赛博乐园，你的答案应该是 $−1$。

实现细节

你需要实现以下函数：

double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr);

• $N$ : 国家的数量。
• $M$ : 双向道路的数量。
• $K$: “除以 $2$ 的能力”的最大使用次数。
• $H$: 国家“赛博乐园”的标号。
• $x, y, c$: 三个长度为 $M$ 的数组。三元组 $(x[i], y[i], c[i])$ 表示第 $i$ 条用来连接国家 $x[i]$ 和 $y[i]$ 的双向边，通过它的时间消耗是 $c[i]$。
• $arr$: 一个长度为 $N$ 的数组。$arr[i]$ 表示国家 $i$ 的特殊能力。
• 如果你能到达赛博乐园，调用该函数应返回从你的国家到达赛博乐园的最短时间，如果你不能，则返回 $−1$。
• 这个过程可能会被多次调用。

假设选手的答案为 $ans_1$ ，标准输出为 $ans_2$ ，当且仅当 $\dfrac{|ans_1-ans_2|}{\max\{ans_2,1\}} \le 10 ^ {-6}$ 时你的输出被视为是正确的。

注意：由于函数调用可能会发生多次，选手需要注意之前调用的残余数据对于后续调用的影响。

输入格式

评测程序示例读取如下格式的输入：

• 第 $1$ 行: $T$

对于 $T$ 组测试数据中的每一个: - 第 $1$ 行: $N \ M \ K$ - 第 $2$ 行: $H$ - 第 $3$ 行: $arr[0] \ arr[1] \ arr[2] \ \cdots \ arr[N − 1]$ - 第 $4 + i(0 \le i \le M − 1)$ 行: $x[i] \ y[i] \ c[i]$

输出格式

评测程序示例按照如下的格式打印你的答案：

对于每组测试数据：

• 第 $1$ 行: 调用 solve 的返回值

样例 1

input

3 2 30
2
1 2 1
1 2 12
2 0 4

output

4

样例 2

input

4 4 30
3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4

output

2

提示

例子

样例 1

考虑下面的调用：

solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});

唯一的到达赛博乐园的路径是 $0 \rightarrow 2$，因为你到达了赛博乐园之后不能再移动到其他任何地方。通行时间的计算过程如下：

样例 2

考虑下面的调用：

solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1});

从你的国家到赛博乐园有两条路径：$0 \rightarrow 1 \rightarrow 3$ 和 $0 \rightarrow 2 \rightarrow 3$。

如果选择路径 $0 \rightarrow 1 \rightarrow 3$，通行时间的计算如下：

如果选择路径 $0 \rightarrow 2 \rightarrow 3$，通行时间的计算如下：

所以，上述调用应该返回 $2$。

约束条件

• $2 \le N \le 10^5 , \sum N \le 10^5$.
• $0 ≤ M ≤ \min\{10^5, \dfrac{N(N-1)}{2} \}, \sum M ≤ 10^5$.
• $1 \le K \le 10^6$.
• $1 \le H < N$
• $0 \le x[i], y[i] < N , x[i] \neq y[i]$.
• $1 \le c[i] \le 10^9$.
• $arr[i] \in \{0, 1, 2\}$.
• 保证每两个国家之间至多使用一条道路进行连接。

子任务

1. (5 分)：$N \le 3, K \le 30$.
2. (8 分)：$M = N − 1, K \le 30, arr[i] = 1$，你可以通过这 $M$ 条道路从任意国家到另外一个国家。
3. (13 分)：$M = N − 1, K \le 30, arr[i] \in \{0, 1\}$，你可以通过这 $M$ 条道路从任意国家到另外一个国家。
4. (19 分)：$M = N − 1, K \le 30, x[i] = i, y[i] = i + 1$.
5. (7 分)：$K \le 30, arr[i] = 1$.
6. (16 分)：$K \le 30, arr[i] \in \{0, 1\}$.
7. (29 分)：$K \le 30$.
8. (3 分)：没有特殊限制。