[Wf2016]Branch Assignment

时间限制:30s      空间限制:128MB

题目描述

要完成一个由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

提示

没有写明提示


题目来源

鸣谢Yts1999上传,lbn187提供译文