Shop and Ship

In Doubleclickland there are $N$ cities ($N \le 5000$). The cities are connected by trade routes, and there are $T$ trade routes in total ($0 \le T \le 25000000$). Each trade route connects two cities $x$ and $y$ and has a shipping cost $C(x, y)$, where $0 \le C(x, y) \le 10000$ and $C(x, y) = C(y, x)$.

Of the $N$ cities, $K$ of them ($1 \le K \le N$) have an online store that sells very nice pencils. A pencil bought in city $x$ costs $P_x$ ($0 \le P_x \le 10000$).

You want to buy one pencil online and have it shipped to a specific city $D$ ($1 \le D \le N$) using the cheapest possible sequence of trade routes. Buying the pencil directly in city $D$ requires no shipping. Find the minimum total cost to obtain one pencil in city $D$.

The first line contains $N$, the number of cities. The cities are numbered from $1$ to $N$.

The second line contains $T$, the number of trade routes.

Each of the next $T$ lines contains three integers $x$, $y$, and $C(x, y)$, meaning that the shipping cost of the trade route between cities $x$ and $y$ is $C(x, y)$.

The next line contains $K$, the number of cities that have an online pencil store.

Each of the next $K$ lines contains two integers $z$ and $P_z$, meaning that a pencil in city $z$ costs $P_z$.

The last line contains $D$, the destination city.

Print the minimum total cost of buying one pencil online and shipping it to city $D$.