#4609. [Wf2016]Branch Assignment

内存限制:128 MiB 时间限制:30 Sec

题目描述

要完成一个由s个子项目组成的项目,给b(b>=s)个部门分配,从而把b个部门分成s个组。分组完成后,每一组的任
意两个点之间都要传递信息。假设在(i,j)两个点间传送信息,要先把信息加密,然后快递员从i出发到总部,再加
密,在到j点。出于安全原因,每次只能携带一条消息。现在给出了道路网络、各个部门和总部的位置,请输出快
递员要走的最小总距离。

输入格式

第一行包含四个整数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)的双向边。保证没有重边,保证图强连通。

输出格式

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

样例

样例输入


			
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

数据范围与提示