The year 3742 has arrived, and now it is Cyberland's turn to host the APIO. In this world, there are ~N~ countries indexed from ~0~ to ~N-1~, along with ~M~ bidirectional roads (allowing travel in both directions) indexed from ~0~ to ~M-1~. The ~i~-th road ~(0 \le i < M)~ connects two different countries, ~x[i]~ and ~y[i]~, and requires a certain amount of time ~c[i]~ to travel across. All participants have gathered in Cyberland for the APIO, except for your country. You are living in country ~0~, and Cyberland is country ~H~. As the cleverest person in your country, your assistance is urgently needed once again. To be more specific, you are asked to determine the minimum time required to reach Cyberland from your country.

Some countries can reset the amount of time you've spent traveling. Also, some countries can divide your total travel time by ~2~ (divide-by-2 ability). You can visit a country repeatedly. Every time you visit a country, you may choose whether to use the special ability in the country. However, you can use the special ability at most once in a single visit (but the special ability can be still be used multiple times by visiting the country multiple times). Moreover, you can only use the divide-by-2 ability at most ~K~ times in fear of being caught by the Cyberland Chemistry Foundation. Once you have reached Cyberland, you cannot move anywhere because the great APIO contest will be held soon.

An array ~arr~ is given, where ~arr_i~ ~(0 \le i < N)~ represents the special ability of country ~i~. There are ~3~ types of special abilities:

• ~arr_i = 0~, means this country sets the travel time to ~0~.
• ~arr_i = 1~, means the travel time remains unchanged at this country.
• ~arr_i = 2~, means this country divides the travel time by ~2~.

It is guaranteed that ~arr_0 = arr_H = 1~ holds. In other words, Cyberland and your country do not have any special abilities.

Your country does not want to miss any moment of APIO, so you need to find the minimum amount of time to reach Cyberland. If you cannot reach Cyberland, your answer should be ~-1~.

Implementation Details

You need to implement the following function:

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~: The number of countries.
• ~M~: The number of bidirectional roads.
• ~K~: The limit on divide-by-2 ability usage.
• ~H~: The index of the country Cyberland.
• ~x, y, c~: three arrays of length ~M~. the tuple ~(x[i], y[i], c[i])~ represents the ~i~-th undirected edge which connects countries ~x[i]~ and ~y[i]~ with time cost ~c[i]~.
• ~arr~: an array of length ~N~. ~arr[i]~ represents the special ability of country ~i~.
• This procedure should return the minimum amount of time to reach Cyberland from your country if you can reach Cyberland, and ~-1~ if you cannot do so.
• This procedure can be called more than once.

Assume that the return value of the contestant is ~ans_1~, and the return value of the reference solution is ~ans_2~, your return value is considered correct if and only if ~\frac{|ans_1 - ans_2|}{\max(ans_2, 1)} \le 10^{-6}~.

Note: Since the procedure can be called more than once, contestants need to pay attention to the impact of the remaining data of the previous call on the current call.

Example 1

Consider the following call:

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

The only path to Cyberland is ~0 \to 2~, because you cannot move to anywhere after reaching Cyberland. The calculation of travel time is as shown below.

country number	travel time
~0~	~0~
~2~	~0 + 4 \to 4~ (sum) ~\to 4~ (special ability)

Therefore, the procedure should return ~4~.

Example 2

Consider the following call:

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

Two paths from your country to Cyberland are ~0 \to 1 \to 3~ and ~0 \to 2 \to 3~.

If your path is ~0 \to 1 \to 3~, the calculation of travel time is as shown below.

country number	travel time
~0~	~0~
~1~	~0 + 5 \to 5~ (sum) ~\to 0~ (special ability)
~3~	~0 + 2 \to 2~ (sum) ~\to 2~ (special ability)

If your path is ~0 \to 2 \to 3~, the calculation of travel time is as shown below.

country number	travel time
~0~	~0~
~2~	~0 + 4 \to 4~ (sum) ~\to 2~ (special ability)
~3~	~2 + 4 \to 6~ (sum) ~\to 6~ (special ability)

Therefore, the procedure should return ~2~.

Constraints

• ~2 \le N \le 10^5~, and ~\sum{N} \le 10^5~.
• ~0 \le M \le \min(10^5, \frac{N(N-1)}{2})~, and ~\sum{M} \le 10^5~.
• ~1 \le K \le 10^6~.
• ~1 \le H < N~.
• ~0 \le x[i],y[i] < N~, and ~x[i] \neq y[i]~.
• ~1 \le c[i] \le 10^9~.
• ~arr[i] \in \{0,1,2\}~.
• It is guaranteed that every pair of countries is connected by at most one road.

Subtasks

1. (5 points): ~N \le 3, K \le 30~.
2. (8 points): ~M = N-1, K \le 30, arr[i] = 1~, you can travel from any country to any other country via the ~M~ edges.
3. (13 points): ~M = N-1, K \le 30, arr[i] \in \{0,1\}~, you can travel from any country to any other country via the ~M~ edges.
4. (19 points): ~M = N-1, K \le 30, x[i] = i, y[i] = i+1~.
5. (7 points): ~K \le 30, arr[i] = 1~.
6. (16 points): ~K \le 30, arr[i] \in \{0,1\}~.
7. (29 points): ~K \le 30~.
8. (3 points): No additional constraints.

Sample Grader

The sample grader reads input in the following format:

• line ~1~: ~T~

For each of the following ~T~ test cases:

• line ~1~: ~N~ ~M~ ~K~
• line ~2~: ~H~
• line ~3~: ~arr[0]~ ~arr[1]~ ~arr[2]~ ~\ldots~ ~arr[N-1]~
• line ~4+i~ ~(0 \le i \le M -1)~: ~x[i]~ ~y[i]~ ~z[i]~

The sample grader prints your answers in the following format:

For each test case:

• line ~1~: the return value of solve

Attachment Package

The sample grader along with sample test cases are available here: cyberland.zip.