경로 우회

어떤 나라의 도로망은 $N$개의 도시를 모두 이어 준다. 어느 도시에서 출발하든 이미 있는 도로만 이용해 나머지 모든 도시에 도착할 수 있다. 도로 하나는 서로 다른 두 도시를 잇고 양방향으로 통행할 수 있으며, 요금소가 하나씩 있다. 통행료는 두 방향 모두에서 낸다. 도로는 도시에서만 만난다. 두 도시를 잇는 도로가 둘 이상인 경우는 없다.

디아스 운송은 도시 사이의 화물 배송 서비스를 운영한다. 화물 하나는 도시 $A$에서 다른 도시 $B$로 옮겨야 한다. 회사는 화물마다 도시 $C$개와 도로 $C-1$개로 이루어진 서비스 경로를 정한다. 서비스 경로의 첫 도시가 화물의 출발지, 마지막 도시가 도착지다. 서비스 경로는 같은 도시를 두 번 지나지 않고, 배송을 맡은 차량은 정해진 서비스 경로로만 달릴 수 있다.

그런데 어느 날 배송 중이던 차량이 고장 났다. 차량은 서비스 경로에 속하지 않은 도시로 옮겨져 수리를 받았다. 회사는 수리를 마친 도시에서 출발해 화물을 도착지까지 배달하는 데 드는 최소 통행료 총액을 알고 싶다. 여기에 제약이 하나 더 붙는다. 차량이 도중에 서비스 경로에 속한 도시를 지나면, 그 도시부터는 다시 서비스 경로를 따라가야 한다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 네 정수 $N$, $M$, $C$, $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$). 차례로 나라의 도시 수, 도로 수, 서비스 경로에 속한 도시 수, 차량을 수리한 도시를 뜻한다. 도시는 $0$부터 $N-1$까지의 정수로 구분한다. 서비스 경로는 $0, 1, \ldots, C-1$이다. 즉 출발지가 $0$이고, $0$에서 $1$로, $1$에서 $2$로 이어져 도착지 $C-1$까지 간다.

이어지는 $M$개의 줄은 나라의 도로망을 설명한다. 각 줄에는 도로 하나를 나타내는 세 정수 $U$, $V$, $P$가 주어진다 ($0 \le U, V \le N-1$, $U \neq V$, $0 \le P \le 250$). 도시 $U$와 도시 $V$를 잇는 도로가 있고 그 통행료가 $P$라는 뜻이다.

마지막 테스트 케이스 다음 줄에는 공백으로 구분된 네 개의 $0$이 주어진다.

각 테스트 케이스마다 한 줄에 정수 $T$ 하나를 출력한다. $T$는 차량이 도착지에 이르는 데 필요한 최소 통행료 총액이다.