公元 3742 年已经到来，现在轮到 Cyberland 主办 APIO 了。在这个世界中，有 $N$ 个国家，编号从 $0$ 到 $N - 1$，以及 $M$ 条双向道路，编号从 $0$ 到 $M - 1$。第 $i$ 条道路（$0 \le i < M$）连接两个不同的国家 $x[i]$ 和 $y[i]$，通过该道路需要花费 $c[i]$ 的时间。除了你的国家外，所有参赛者都已经聚集在 Cyberland 参加 APIO。你居住在国家 $0$，而 Cyberland 是国家 $H$。作为你们国家最聪明的人，现在再次急需你的帮助。具体来说，你需要确定从你的国家到达 Cyberland 所需的最短时间。

有些国家可以清除你的总通行时间。此外，有些国家可以将你的总通行时间除以 2（除以 2 能力）。你可以多次访问同一个国家。每次访问一个国家时，你可以选择是否使用该国家的特殊能力。但你在单次访问中最多只能使用一次特殊能力（这意味着通过多次访问该国家，可以多次使用特殊能力）。此外，为了防止被 Cyberland 化学基金会抓住，你最多只能使用 $K$ 次除以 2 的能力。一旦你到达了 Cyberland，你就不能再移动到任何地方，因为伟大的 APIO 竞赛即将举行。

给定一个数组 $arr$，其中 $arr_i$（$0 \le i < N$）表示国家 $i$ 的特殊能力。特殊能力有 3 种类型： $arr_i = 0$，表示该国家使通行时间变为 0。 $arr_i = 1$，表示在该国家通行时间保持不变。 * $arr_i = 2$，表示该国家将通行时间除以 2。

保证 $arr_0 = arr_H = 1$。换句话说，Cyberland 和你的国家没有任何特殊能力。

你的国家不想错过 APIO 的任何时刻，因此你需要找到到达 Cyberland 的最短时间。如果你无法到达 Cyberland，你的答案应该是 $-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$：Cyberland 的国家编号。
• $x, y, c$：三个长度为 $M$ 的数组。元组 $(x[i], y[i], c[i])$ 表示第 $i$ 条无向边，连接国家 $x[i]$ 和 $y[i]$，时间花费为 $c[i]$。
• $arr$：一个长度为 $N$ 的数组。$arr[i]$ 表示国家 $i$ 的特殊能力。
• 如果可以到达 Cyberland，该过程应返回从你的国家到达 Cyberland 的最短时间，否则返回 $-1$。
• 此过程可以被调用多次。

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

注意：由于该过程可以被调用多次，选手需要注意前一次调用的剩余数据对当前调用的影响。

样例

输入格式 1

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

输出格式 1

4

说明

到达 Cyberland 的唯一路径是 $0 \to 2$，因为到达 Cyberland 后你不能移动到任何地方。通行时间的计算如下： 国家 0：0 国家 2：$0 + 4 \to 4$ (总和) $\to 4$ (特殊能力)

输入格式 2

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

输出格式 2

2

说明

从你的国家到 Cyberland 有两条路径。它们是：$0 \to 1 \to 3$ 和 $0 \to 2 \to 3$。 如果你的路径是 $0 \to 1 \to 3$，通行时间的计算如下： 国家 0：0 国家 1：$0 + 5 \to 5$ (总和) $\to 0$ (特殊能力) 国家 3：$0 + 2 \to 2$ (总和) $\to 2$ (特殊能力) 如果你的路径是 $0 \to 2 \to 3$，通行时间的计算如下： 国家 0：0 国家 2：$0 + 4 \to 4$ (总和) $\to 2$ (特殊能力) 国家 3：$2 + 4 \to 6$ (总和) $\to 6$ (特殊能力)

数据范围

• $2 \le N \le 10^5$，且 $\sum N \le 10^5$。
• $0 \le M \le \min\{10^5, \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] \neq y[i]$。
• $1 \le c[i] \le 10^9$。
• $arr[i] \in \{0, 1, 2\}$。
• 保证每对国家之间最多由一条道路连接。
• 时间限制：4 秒。

子任务

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 分)：无附加限制。

样例评测程序

样例评测程序按以下格式读取输入：

• 第 1 行：$T$
• 对于接下来的 $T$ 个测试用例：
  • 第 1 行：$N \ M \ K$
  • 第 2 行：$H$
  • 第 3 行：$arr[0] \ arr[1] \ arr[2] \dots arr[N - 1]$
  • 第 $4 + i$ 行（$0 \le i \le M - 1$）：$x[i] \ y[i] \ z[i]$

样例评测程序按以下格式打印你的答案：

• 对于每个测试用例：
  • 第 1 行：solve 的返回值