#2006. [Wf2016]Branch Assignment

[Wf2016]Branch Assignment

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