시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 32 12 9 33.333%

문제

Innovative Consumer Products Company (ICPC)는 비밀 프로젝트를 시작하려하고 있다. 이 프로젝트는 s개의 하위 프로젝트로 구성된다. 이 프로젝트에 관련된 b(≥s)개의 ICPC의 지사들이 있고, ICPC는 각 지사에 하위 프로젝트들 중 하나를 맡기고자 한다. 다시 말하자면, 지사들은 s개의 분리된 그룹으로 나누어지고, 각 그룹이 한 하위 프로젝트를 맡게 된다.

각 달의 마지막에, 각 지사는 그 그룹에 있는 다른 모든 지사에게 메시지를 보낼 것이다(서로 다른 지사에는 다른 메시지를 보낸다). ICPC는 통신을 위한 특별한 프로토콜을 가지고 있다. 각 지사 i는 그 지사와 본부에만 공개된 비밀키 kI를 가지고 있다. 지사 i가 지사 j에 메시지를 보내고 싶어한다고 하자. 지사 i는 비밀키 kI로 메시지를 암호화한다. 신뢰할 수 있는 운반원이 이 메시지를 지사로부터 본부까지 전달한다. 본부는 키 kI로 메시지를 복호화하고, 키 kj로 다시 암호화시킨다. 운반원은 새롭게 암호화된 메시지를 (키 kj를 가지고 있는) 지사 j로 전달한다. 보안적인 문제 때문에, 운반원은 동시에 오직 하나의 메시지만 전달할 수 있다.

도로망과 지사와 본부의 위치가 주어졌을 때, 당신은 각 지사에 하위 프로젝트를 배정하는 모든 경우에 대해서, 월말에 운반원이 메시지를 전달하기 위해 이동해야하는 최소 거리를 알아내야 한다.

입력

입력의 첫줄은 4개의 정수 n, b, s, 그리고 r로 이루어진다. n (2 ≤ n ≤ 5 000)은 교차로의 개수, b (1 ≤ b ≤ n − 1)는 지사의 수, s (1 ≤ s ≤ b)는 하위 프로젝트의 수, r (1 ≤ r ≤ 50 000)은 도로의 수를 나타낸다. 교차로들은 1부터 n까지 숫자가 주어지고, 지사들은 교차로 1부터 교차로 b에 위치하고, 본부는 교차로 b+1에 위치한다. 다음 r개의 줄은 각각 3개의 정수 u, v, l로 이루어진다. 이것은 교차로 u에서 교차로 v로 가는 길이 있고(1 ≤ u, v ≤ n), 이 길이가 l(0 ≤ ℓ ≤ 10 000)임을 뜻한다. u에서 v로 가는 길은 두번 이상 주어지지 않고, 어느 교차로에서든 다른 모든 교차로로 갈 수 있음이 보장된다.

출력

운반원이 이동해야 할 최소 거리를 출력한다.

예제 입력

5 4 2 10
5 2 1
2 5 1
3 5 5
4 5 0
1 5 1
2 3 1
3 2 5
2 4 5
2 1 1
3 4 2

예제 출력

13

예제 입력 2

5 4 2 10
5 2 1
2 5 1
3 5 5
4 5 10
1 5 1
2 3 1
3 2 5
2 4 5
2 1 1
3 4 2

예제 출력 2

24

힌트

출처

ACM-ICPC > World Finals > 2016 World Finals B번