쇼핑과 배송

더블클릭랜드에는 $N$개의 도시가 있다 ($N \le 5000$). 도시들은 무역로로 연결되어 있으며, 무역로는 모두 $T$개이다 ($0 \le T \le 25000000$). 각 무역로는 두 도시 $x$와 $y$를 잇고 배송 비용 $C(x, y)$를 가지며, $0 \le C(x, y) \le 10000$이고 $C(x, y) = C(y, x)$이다.

$N$개의 도시 중 $K$개 ($1 \le K \le N$)에는 아주 좋은 연필을 파는 온라인 상점이 있다. 도시 $x$에서 산 연필 한 자루의 가격은 $P_x$이다 ($0 \le P_x \le 10000$).

연필 한 자루를 온라인으로 사서, 특정 도시 $D$ ($1 \le D \le N$)까지 가장 저렴한 무역로 경로를 이용해 배송하려고 한다. 도시 $D$에서 직접 사면 배송비가 들지 않는다. 도시 $D$에서 연필 한 자루를 얻는 데 드는 최소 총 비용을 구하여라.

첫째 줄에 도시의 수 $N$이 주어진다. 도시는 $1$번부터 $N$번까지 번호가 매겨져 있다.

둘째 줄에 무역로의 수 $T$가 주어진다.

다음 $T$개의 줄에는 각각 세 정수 $x$, $y$, $C(x, y)$가 주어지며, 도시 $x$와 $y$를 잇는 무역로의 배송 비용이 $C(x, y)$임을 나타낸다.

다음 줄에는 온라인 연필 상점이 있는 도시의 수 $K$가 주어진다.

다음 $K$개의 줄에는 각각 두 정수 $z$와 $P_z$가 주어지며, 도시 $z$의 연필 가격이 $P_z$임을 나타낸다.

마지막 줄에는 목적지 도시 $D$가 주어진다.

연필 한 자루를 온라인으로 사서 도시 $D$까지 배송하는 데 드는 최소 총 비용을 출력한다.