고속도로 주유 계획

운송 회사가 도움을 청해 왔다. 트럭에 넣는 연료비는 이 회사의 가장 큰 지출 가운데 하나여서, 회사는 연료비를 최대한 줄이고 싶어 한다.

운행 거리가 길어서 운전기사는 보통 주유소 여러 곳에 들러 연료를 넣는다. 연료 가격은 주유소마다 다르다. 가격 차이가 워낙 커서 값싼 주유소에 들르려고 길을 돌아가는 편이 이득일 때도 있다. 가격은 날마다 바뀌지만 하루 동안은 그대로다.

회사는 매일 아침 그날 모든 주유소의 연료 가격을 알아낸다. 목적지마다 도로망에서 필요한 부분만 추린 단순 그래프도 있는데, 주요 교차로와 주유소만 정점으로 들어 있다. 각 도로를 지나는 데 드는 연료의 양도 밀리리터 단위까지 정확히 안다. 이 양은 어느 방향으로 가는지, 탱크에 연료가 얼마나 남았는지와 상관없다. 운전기사는 연료를 밀리리터 단위로 넣을 수 있다.

트럭이 주유소나 목적지에 닿는 바로 그 순간에 연료가 떨어져도 괜찮다. 연료 소모가 조금씩 달라지는 것에 대비한 예비 탱크가 있지만 그 연료는 쓰지 않기로 되어 있으므로, 없다고 생각한다.

연료 탱크의 용량에는 한계가 있다. 목적지까지 가는 경로와 주유 방법을 정해서 연료비를 가장 적게 쓰는 방법을 구하라.

첫 줄에 테스트 케이스의 개수가 주어진다. 이 수는 양의 정수이고 100 이하다. 각 테스트 케이스는 다음과 같다.

• 첫 줄에 정점의 수 $n$, 도로의 수 $m$, 주유소의 수 $s$가 공백을 사이에 두고 주어진다. ($2 \le n \le 1000$, $1 \le m \le 10000$, $1 \le s \le 120$)
• 다음 줄에 연료 탱크의 용량 $t$가 밀리리터 단위로 주어진다. ($1 \le t \le 100000$)
• 다음 $m$개의 줄에는 정수 $a$, $b$, $f$가 공백을 사이에 두고 주어진다. 정점 $a$와 정점 $b$를 잇는 도로가 있고, 이 도로를 지나려면 연료 $f$밀리리터가 든다. ($1 \le a, b \le n$, $a \ne b$, $1 \le f \le 100000$)
• 다음 $s$개의 줄에는 정수 $x$와 $p$가 공백을 사이에 두고 주어진다. 정점 $x$에 주유소가 있고, 그곳에서 연료 1밀리리터의 가격은 $p$다. ($1 \le x \le n$, $1 \le p \le 100$)
• 마지막 줄에는 회사가 있는 정점 $c$와 목적지 정점 $d$가 공백을 사이에 두고 주어진다. ($1 \le c, d \le n$, $c \ne d$)

모든 도로는 양방향이다. 두 정점을 잇는 도로는 많아야 하나다. 회사 바로 옆에 주유소가 있으므로 정점 $c$에는 항상 주유소가 있다. 트럭은 빈 탱크로 출발한다. 목적지에는 항상 도달할 수 있다.

각 테스트 케이스마다 연료비로 써야 하는 최소 금액을 한 줄에 출력한다.