3534：Escape of Life and Death

During his ambitious adventure in search of treasure, Yangyang discovered an ancient underground palace. After thoroughly exploring the palace, he found that it was constructed with elaborately decorated chambers connected by fortified corridors. Out of an explorer’s instinct, he sketched a complete map of the palace before entering the largest and most magnificent chamber, which lied in the heart of the palace.

Standing at the center of the chamber, Yangyang looked around and was profoundly amazed by those vivid, huge statues of the gods. He recognized the tallest one, which depicted God Proxima holding his sacred cane. All of a sudden, a voice took Yangyang by surprise, “Leave now, you stupid human!” It was loud but sounded as if it came from the distance. A thought of danger immediately flashed through Yangyang’s mind: his intrusion into the palace had triggered a spell of destruction. Now an earthquake was emerging from right under the chamber and growing more and more violent. He must escape from underground for life as quickly as possible.

Yangyang knew that seismic waves propagated isotropically at a constant speed. If they spread across any chamber, the chamber would collapse, trap anybody inside and become impassable. However, the corridors were adequately solid to stand any impact of earthquake. Driven by his fearless but obstinate character, Yangyang would only allow himself to run from one chamber to another one which was farther away from the epicenter except when he was going to run toward chamber n + 1.

Yangyang had measured the location of each chamber and estimated the time he needed to run through each corridor. How soon could he accomplish the escape of life and death?

The input consists of a single test case. The first line of input contains three integers n, m, v (1 ≤ n ≤ 50,000, 1 ≤ m ≤ 200,000, 1 ≤ v ≤ 1,000). Next come n lines, each containing a pair of integers (x_i, y_i) (−10⁹ ≤ x_i, y_i ≤ 10⁹, ∀1 ≤ i ≤ n). The following m lines each contains three integers a_i, b_i, t_i (0 ≤ a_i, b_i ≤ n + 1, 1 ≤ t_i ≤ 1,000, ∀1 ≤ i ≤ m). The last line contains two pairs of integers (x₀, y₀), (x_n+1, y_n+1) (−10⁹ ≤ x₀, y₀, x_n+1, y_n+1 ≤ 10⁹).

There were n + 2 chambers in total, numbered 0 through n + 1. Chamber 0 was where Yangyang found the statue of God Proxima; chamber n + 1 was located, as the only exception, on the ground and would not trap Yangyang even if it collapsed. Chamber i (1 ≤ i ≤ n) was located at (x_i, y_i). Corridor i (1 ≤ i ≤ m) connected chambers a_i and b_i, and Yangyang needed t_i units of time to run through it. Seismic waves propagated at constant speed v.

If Yangyang could escape, output the minimum time he needed; otherwise, output “Impossible”.

As can be inferred from the sample test case, if seismic waves reached a chamber at the very moment Yangyang began to escape from it, he would still get trapped.