\begin{problem}{Highway Hassle}{\textsl{standard input}}{\textsl{standard output}}{1 second}{256 mebibytes}{}

A transport company has come to you for help. One of the
biggest expenses that they have is the petrol for the trucks.
They would like to minimize the money they need to spend
on petrol.

Because of the long trips, a truck driver typically needs
to stop multiple times at a petrol station to tank up. What
complicates matters is that the price of petrol is not the same
at every station. The differences could in fact be so significant
that it pays to take a detour in order to visit a station with a
low price. Yet another complication is that the price is not the
same every day (but it does not change during the day).
The good news is that they can find out, every morning,
what the price of petrol is at every station for that day. They
also have, for every destination, a simple graph representing
the relevant part of the road network, containing only the major intersections and petrol sta-
tions as nodes. Furthermore, they know for every road exactly how much petrol is needed to
go from one node to the other, down to the milliliter; it does not depend on the direction or
the amount of petrol in the tank. The truck drivers also have the ability to tank with milliliter
precision.

It is perfectly fine for a truck to run out of petrol at the exact moment it arrives at a petrol
station or at the destination; there is in fact a spare tank to allow for small fluctuations in
fuel consumption, but that petrol is not supposed to be used. You may therefore ignore its
existence.

A final thing to take into consideration is that the trucks have a fuel tank of limited size.
With all that information, can you work out what the optimal path to the destination is, along
with the optimal tanking strategy?

\InputFile

On the first line one positive number: the number of test cases, at most 100. After that per test
case:

\begin{itemize}

\item one line with three space-separated integers $n$, $m$ and $s$ ($2 \le n \le 1 000$ and $1 \le m \le 10^4$ and $1 \le s \le 120$): the number of nodes, edges and petrol stations, respectively.
\item one line with a single integer $t$ ($1 \le t \le 10^5$): the maximum amount of petrol that
the fuel tank can hold in milliliters.
\item $m$ lines, each with three space-separated integers $a$, $b$ and $f$ ($1 \le a, b \le n$, $a = b$, $1 \le f \le 10^5$), indicating that there is a road between nodes $a$ and $b$ which takes $f$ milliliters of petrol (fuel) to traverse.
\item $s$ lines, each with two space-separated integers $x$ and $p$ ($1 \le x \le n$ and $1 \le p \le 100$):
the node $x$ where each petrol station is located and the price p per milliliter of petrol at
that station, respectively.
\item one line with two space-separated integers $c$ and $d$ ($1 \le c, d \le n$ and $c = d$): the nodes
where the company and the destination are located, respectively.
\end{itemize}

Every road is bidirectional. There is at most one road between any pair of nodes. There is
always a petrol station at node $c$ (it is right next to the company). The truck starts with an
empty tank. The destination is guaranteed to be reachable.

\OutputFile

Per test case: one line with a single integer: the minimum amount of money that needs to be spent on
petrol.

\Examples
\begin{example}
\exmp{
3
3 3 2
2000
1 3 800
1 2 500
2 3 500
1 70
2 40
1 3
5 5 3
1000
1 2 800
2 5 800
1 3 400
3 4 600
4 5 600
1 80
2 90
3 20
1 5
4 3 3
1000
1 2 200
2 3 600
3 4 300
1 40
2 70
3 90
2 4
}{
55000
134000
61000
}%
\end{example}
\end{problem}

