Description

创新消费品公司（ICPC）计划启动一个绝密项目。该项目由 $s$ 个子项目组成。将有 $b \ge s$ 个 ICPC 的分支机构参与此项目，ICPC 希望将每个分支机构分配给一个子项目。换句话说，这些分支机构将形成 $s$ 个不相交的组，每个组负责一个子项目。

每个月底，每个分支机构将向其组内的每个其他分支机构发送一条消息（每个分支机构接收不同的消息）。ICPC 有一个特定的通信协议。每个分支机构 $i$ 有一个只有该分支机构和 ICPC 总部知道的密钥 $k_i$。假设分支机构 $i$ 想要向分支机构 $j$ 发送消息。分支机构 $i$ 用其密钥 $k_i$ 加密消息。一个可信的信使从该分支机构取走消息并将其交付给 ICPC 总部。总部用密钥 $k_i$ 解密消息，并用密钥 $k_j$ 重新加密。然后信使将这个新加密的消息交付给分支机构 $j$，分支机构 $j$ 用其自己的密钥 $k_j$ 解密。出于安全原因，信使一次只能携带一条消息。

给定一个道路网络以及分支机构和总部在此网络中的位置，你的任务是确定信使在所有可能的分支机构到子项目的分配中，传递所有月底消息所需的最小总距离。

Input Format

输入的第一行包含四个整数 $n$、$b$、$s$ 和 $r$，其中 $n$ ($2 \le n \le 5\, 000$) 是交叉路口的数量，$b$ ($1 \le b \le n-1$) 是分支机构的数量，$s$ ($1 \le s \le b$) 是子项目的数量，$r$ ($1 \le r \le 50\, 000$) 是道路的数量。交叉路口编号从 $1$ 到 $n$。分支机构位于交叉路口 $1$ 到 $b$，总部位于交叉路口 $b + 1$。接下来的 $r$ 行中的每一行包含三个整数 $u$、$v$ 和 $\ell$，表示从交叉路口 $u$ 到不同交叉路口 $v$ ($1 \leq u,v \leq n$) 的一条单向道路，长度为 $\ell$ ($0 \leq \ell \leq 10\, 000$)。没有有序对 $(u,v)$ 会出现多次，并且从任何交叉路口都可以到达每个其他交叉路口。

Output Format

输出信使需要行驶的最小总距离。

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

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

24

Hint

时间限制：2000 毫秒，内存限制：1048576 kB。

国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2016。

题面翻译由 ChatGPT-4o 提供。