Highway Hassle

A transport company asks you for help. Petrol for the trucks is one of its largest expenses, and the company wants to spend as little on petrol as it can.

A trip is long, so a driver normally stops at several petrol stations to tank up. The price of petrol is not the same at every station. The gaps can be large enough that a detour to a station with a low price pays off. The price also changes from day to day, but it stays the same for the whole day.

Every morning the company finds out the price of petrol at every station for that day. For every destination it also has a simple graph of the relevant part of the road network, with only the major intersections and the petrol stations as nodes. For every road it knows exactly how much petrol is needed to drive from one node to the other, down to the milliliter. That amount does not depend on the direction or on the amount of petrol in the tank. A driver can tank with milliliter precision.

A truck may run out of petrol at the exact moment it arrives at a petrol station or at the destination. There is a spare tank for small changes in fuel consumption, but that petrol is not supposed to be used, so ignore it.

The fuel tank holds a limited amount of petrol. Work out the route to the destination and the tanking strategy that cost the least money.

The first line holds one positive integer, the number of test cases, at most 100. Each test case then looks like this.

• one line with three space-separated integers $n$, $m$ and $s$ ($2 \le n \le 1000$, $1 \le m \le 10000$, $1 \le s \le 120$): the number of nodes, roads and petrol stations.
• one line with one integer $t$ ($1 \le t \le 100000$): the amount of petrol the fuel tank holds, in milliliters.
• $m$ lines, each with three space-separated integers $a$, $b$ and $f$ ($1 \le a, b \le n$, $a \ne b$, $1 \le f \le 100000$): there is a road between node $a$ and node $b$, and driving it takes $f$ milliliters of petrol.
• $s$ lines, each with two space-separated integers $x$ and $p$ ($1 \le x \le n$, $1 \le p \le 100$): a petrol station sits at node $x$, and one milliliter of petrol costs $p$ there.
• one line with two space-separated integers $c$ and $d$ ($1 \le c, d \le n$, $c \ne d$): the node of the company and the node of the destination.

Every road is bidirectional. There is at most one road between any pair of nodes. Node $c$ always has a petrol station, because it sits right next to the company. The truck starts with an empty tank. The destination is always reachable.

For every test case, print one line with one integer: the minimum amount of money that needs to be spent on petrol.