Route Detour

The road system of a country links all of its $N$ cities, so from any city you can reach every other city over the existing roads. Each road joins two distinct cities, carries traffic in both directions, and has one toll booth. The toll is paid in both directions of travel. Roads meet only at cities. No pair of cities is joined by two or more roads.

Dias Transport runs a parcel delivery service between the cities. Each parcel has to be carried from a city $A$ to another city $B$. For every parcel the company fixes a service route made of $C$ cities and $C-1$ roads. The first city of the service route is the origin of the parcel and the last one is its destination. The service route never visits the same city twice, and the vehicle assigned to a parcel may drive only along the service route it was given.

One day the vehicle on a delivery broke down. It was taken for repair to a city that is not one of the cities on its service route. The company wants the minimum total toll cost for the vehicle to deliver the parcel to the destination city, starting from the city where it was repaired, under one extra restriction: if at some moment the vehicle passes through one of the cities of its service route, from that city on it must follow the service route again.

The input contains several test cases.

The first line of a test case has four integers $N$, $M$, $C$ and $K$ ($4 \le N \le 250$, $3 \le M \le N \times (N-1) / 2$, $2 \le C \le N-1$, $C \le K \le N-1$), giving the number of cities in the country, the number of roads, the number of cities on the service route, and the city where the vehicle was repaired. Cities are identified by integers from $0$ to $N-1$. The service route is $0, 1, \ldots, C-1$: the origin is $0$, from $0$ it goes to $1$, from $1$ to $2$, and so on up to the destination $C-1$.

The next $M$ lines describe the road system of the country. Each of those lines describes one road and has three integers $U$, $V$ and $P$ ($0 \le U, V \le N-1$, $U \neq V$, $0 \le P \le 250$), meaning that a road joins cities $U$ and $V$ with toll cost $P$.

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

For each test case print a single line with a single integer $T$, the minimum total toll cost for the vehicle to reach the destination.