지사 배정

ICPC(Innovative Consumer Products Company)는 비밀 프로젝트를 시작한다. 이 프로젝트는 하위 프로젝트 $s$개로 나뉜다. 프로젝트에 참여하는 지사는 $b$개($b \ge s$)이고, 회사는 각 지사에 하위 프로젝트 하나를 맡긴다. 즉 지사는 서로 겹치지 않는 $s$개의 그룹으로 나뉘고, 한 그룹이 하위 프로젝트 하나를 맡는다. 빈 그룹은 없다.

매달 말에 각 지사는 같은 그룹의 다른 모든 지사에게 메시지를 보낸다. 받는 지사마다 내용이 다른 메시지를 보낸다. 회사는 통신에 특별한 프로토콜을 쓴다. 지사 $i$에는 그 지사와 본부만 아는 비밀키 $k_i$가 있다. 지사 $i$가 지사 $j$에게 메시지를 보내려면 먼저 지사 $i$가 $k_i$로 메시지를 암호화한다. 운반원이 그 메시지를 지사에서 본부까지 옮긴다. 본부는 $k_i$로 메시지를 복호화한 뒤 $k_j$로 다시 암호화한다. 운반원은 새로 암호화된 메시지를 $k_j$를 가진 지사 $j$까지 옮긴다. 보안 때문에 운반원은 한 번에 메시지 하나만 옮길 수 있다.

그래서 메시지 하나를 배달하는 거리는 보내는 지사에서 본부까지의 최단 거리에 본부에서 받는 지사까지의 최단 거리를 더한 값이고, 월말에 운반원이 이동하는 거리는 그달에 배달하는 모든 메시지의 거리를 더한 값이다.

도로망과 지사, 본부의 위치가 주어진다. 지사에 하위 프로젝트를 배정하는 방법을 모두 살펴보고, 월말에 운반원이 이동해야 하는 거리의 최솟값을 구하라.

첫 줄에 정수 네 개 $n$, $b$, $s$, $r$가 주어진다. $n$($2 \le n \le 5000$)은 교차로의 개수, $b$($1 \le b \le n-1$)는 지사의 수, $s$($1 \le s \le b$)는 하위 프로젝트의 수, $r$($1 \le r \le 50000$)은 도로의 수다. 교차로에는 $1$번부터 $n$번까지 번호가 붙어 있다. 지사는 교차로 $1$번부터 교차로 $b$번에 있고, 본부는 교차로 $b+1$번에 있다.

다음 $r$개의 줄에는 각각 정수 세 개 $u$, $v$, $l$이 주어진다. 교차로 $u$에서 교차로 $v$로 가는 길이 있고 그 길의 길이가 $l$이라는 뜻이다($1 \le u, v \le n$, $0 \le l \le 10000$). 길은 주어진 방향으로만 지날 수 있다. $u$에서 $v$로 가는 길은 두 번 이상 주어지지 않고, 어느 교차로에서든 다른 모든 교차로로 갈 수 있음이 보장된다.

운반원이 이동해야 하는 거리의 최솟값을 출력한다.