Description

要完成一个由s个子项目组成的项目，给b(b>=s)个部门分配，从而把b个部门分成s个组。分组完成后，每一组的任

意两个点之间都要传递信息。假设在(i,j)两个点间传送信息，要先把信息加密，然后快递员从i出发到总部，再加

密，在到j点。出于安全原因，每次只能携带一条消息。现在给出了道路网络、各个部门和总部的位置，请输出快

递员要走的最小总距离。

Format

Input

第一行包含四个整数n,b,s,r。n(2<=n<=5000)代表路口数，b(1<=b<=n-1)是部门数，s(1<=s<=b)是子项目数

r(1<=r<=50000)是道路数。路口标号为1~n，部门在路口1~b，总部在路口b+1。

接下来r行每行三个整数u,v,l，描述一条从u到v长度为l(0<=l<=10000)的双向边。保证没有重边，保证图强连通。

Output

输出快递员要走的最小总距离。

Samples

5 4 3 8
1 5 15
5 1 15
2 5 2
5 2 3
3 5 1
5 3 1
4 5 2
5 4 0

4