The MAPS design team is preparing the Olympic fencing venue map. Room ~1~ is the warm-up room, room ~n~ is the final piste, and the team needs the fastest simple route between them before the bout begins.

The venue has ~n~ rooms and ~m~ ordinary corridors. Each corridor connects two different rooms, can be used in both directions, and takes a positive number of seconds to traverse. There is at most one ordinary corridor between any pair of rooms.

Some rooms are marked as shortcut rooms. Between any two different shortcut rooms, MAPS has drawn a hidden referee tunnel that can be used in either direction in exactly ~t~ seconds. Tunnel times are nonnegative: ~t=0~ is allowed and means that moving through a tunnel takes no time.

The fencer must move from room ~1~ to room ~n~ without visiting any room more than once. Find the minimum possible total time. If no such route exists, output Impossible.

Input

The first line contains three integers ~n~, ~m~, and ~t~ (~2 \leq n \leq 10^3~, ~1 \leq m \leq 10^3~, ~0 \leq t \leq 10^6~).

The second line contains a binary string of length ~n~. Its ~i~-th character is 1 if room ~i~ is a shortcut room, and 0 otherwise.

Each of the next ~m~ lines contains three integers ~u_i~, ~v_i~, and ~w_i~ (~1 \leq u_i, v_i \leq n~, ~u_i \neq v_i~, ~1 \leq w_i \leq 10^6~), meaning there is an ordinary corridor between rooms ~u_i~ and ~v_i~ that takes ~w_i~ seconds.

It is guaranteed that no ordinary corridor connects a room to itself, and there is at most one ordinary corridor between any two rooms.

Output

Print the minimum possible total time, or Impossible if no valid route exists.

Example 1

Input

3 2 3
101
1 2 2
2 3 2

Output

3

Example 2

Input

4 4 0
0110
1 2 2
2 3 2
3 4 2
1 4 9

Output

4

Example 3

Input

4 2 10
1000
1 2 1
2 3 1

Output

Impossible