Domestic Networks

Alex is a system administrator at Domestic Networks Inc. The company's network connects apartments across several buildings, and Alex must design a new segment.

He has a map of the apartments to connect and the possible links between them. Each link joins two apartments and has a known length in meters. The goal is to make every apartment connected, possibly indirectly through other apartments.

The company buys cable at the nearest shop, which stocks only category 5 and category 6 cable, priced at p5 and p6 rubles per meter respectively. The shop has only q5 meters of category 5 cable and q6 meters of category 6 cable available.

A construction plan is a set of links to build; each built link is made from a single continuous piece of cable of either category 5 or category 6. The cost of a plan is the total price of all cable it uses. The total length of category 5 cable used must not exceed q5, and the total length of category 6 cable used must not exceed q6.

Help Alex determine the minimum possible cost of a plan that connects all apartments.

The first line contains two integers n and m: the number of apartments and the number of possible links (1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000).

Each of the next m lines describes one possible link with three integers a, b, and l: the two apartments the link can connect and its length in meters (1 ≤ a, b ≤ n, 0 ≤ l ≤ 100). Apartments are numbered from 1 to n.

The last line contains four integers p5, q5, p6, and q6: the price per meter and available quantity of category 5 and category 6 cable respectively (1 ≤ p5, q5, p6, q6 ≤ 10000).

If all apartments can be connected using the available cable, print a single integer: the minimum total cost, in rubles, of a valid plan.

Otherwise, print the single word Impossible.