This page is still under construction.

Parts of this page are still being built. What you see may change.

Highway Hassle

Time limit2sMemory limit256 MB

Summary
Plan the cheapest route and refueling stops for a tank-limited truck when each station charges its own price per milliliter.
Level

Medium7 of 10

Topics
Shortest path, Graph, Heap
Solved
No attempts yet

Problem

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.

Input

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 nn, mm and ss (2≤n≤10002 \le n \le 1000, 1≤m≤100001 \le m \le 10000, 1≤s≤1201 \le s \le 120): the number of nodes, roads and petrol stations.
  • one line with one integer tt (1≤t≤1000001 \le t \le 100000): the amount of petrol the fuel tank holds, in milliliters.
  • mm lines, each with three space-separated integers aa, bb and ff (1≤a,b≤n1 \le a, b \le n, a≠ba \ne b, 1≤f≤1000001 \le f \le 100000): there is a road between node aa and node bb, and driving it takes ff milliliters of petrol.
  • ss lines, each with two space-separated integers xx and pp (1≤x≤n1 \le x \le n, 1≤p≤1001 \le p \le 100): a petrol station sits at node xx, and one milliliter of petrol costs pp there.
  • one line with two space-separated integers cc and dd (1≤c,d≤n1 \le c, d \le n, c≠dc \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 cc 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.

Output

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

Examples2

  1. Example 1

    Input
    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
    Expected output
    55000
134000
61000

  2. Example 2

    Input
    1
2 1 1
100
1 2 100
1 5
1 2
    Expected output
    500