URI Online Judge | 1123

Route Change

Maratona de Programação da SBC Brazil

Timelimit: 1

The road system of a country connects all N cities so that it is possible to travel between any pair of cities using existing roads. Each road connects two different cities, is two-way and one has exactly one toll booth (a toll is paid for both directions of traffic). Roads intersect only in a city and no pair of cities is interconnected by two or more roads.

Dias Transport offers a one-day parcel delivery service between cities. Each parcel must be transported from a city A to another city B. The management of Dias Transport defines, for each parcel, a service route, consisting of C cities and C - 1 roads: the first city on the service route is the origin of the parcel, the final city is the destination of the parcel. The service route never passes twice through the same city, and the vehicle chosen to deliver a parcel can only travel by the service route defined.

One day, however, a vehicle broke down and was taken for repairs in a city that was not among the cities in its service route. The management of Dias Transport wants to know which is the lowest total cost, in terms of tolls, for delivering the parcel (that is, to take the vehicle from the city it was repaired to the destination city), but with an additional constraint: if at some point the vehicle reaches one of the cities that make up its service route, it should go back to following its service route.

Input

The input contains several test cases. The first line of a test case contais four integers N, M, C and K (4 ≤ N ≤ 250, 3 ≤ MN×(N−1)/2, 2 ≤ CN−1 and CKN−1), representing, respectively, the number of cities, the number of roads, the number of cities in the service route and the city where the vehicle was taken for repair. The cities are identified by integers from 0 to N - 1. The service route is 0, 1,..., C - 1, that the origin is 0, from 0 goes to 1, from 1 to 2 and so on, until the destination C - 1. The next M lines describe the road system. Each of those lines describes one road and contains three integers U, V and P (0 ≤ U, VN−1, UV, 0 ≤ P ≤ 250),indicating that there exists a road connecting cities U and V with a toll of cost P.

The last test case is followed by a line containing four zeros separated by blank spaces.

Output

For each test case, your program should print a single line, containing a single integer, the minimum total toll cost for the vehicle to reach the destination city.

Input Sample Output Sample

4 6 3 3
0 1 10
1 2 10
0 2 1
3 0 1
3 1 10
3 2 10
6 7 2 5
5 2 1
2 1 10
1 0 1
3 0 2
3 4 2
3 5 3
5 4 2
5 5 2 4
0 1 1
1 2 2
2 3 3
3 4 4
4 0 5
0 0 0 0

10
6
6