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$。
• 这个过程可能会被多次调用。

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

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

输入格式

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

• 第 $1$ 行: $T$

对于 $T$ 组测试数据中的每一个: - 第 $1$ 行: $NMK$ - 第 $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\to 2$，因为你到达了赛博乐园之后不能再移动到其他任何地方。通行时间的计算过程如下：

样例 2

考虑下面的调用：

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

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

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

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

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

约束条件

• $2\le N\le {10}^5,\sum N\le {10}^5$.
• $0\le M\le min\{{10}^5,{\displaystyle \frac{N(N-1)}{2}}\},\sum M\le {10}^5$.
• $1\le K\le {10}^6$.
• $1\le H<N$
• $0\le x[i],y[i]<N,x[i]\ne 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 分)：没有特殊限制。