Branch Assignment

The Innovative Consumer Products Company (ICPC) is starting a secret project. The project splits into $s$ subprojects. There are $b$ branch offices involved, with $b \ge s$, and the company gives each branch one of the subprojects. In other words, the branches are divided into $s$ disjoint groups, and each group takes one subproject. No group is empty.

At the end of every month, each branch sends a message to every other branch in its own group. The message differs for each recipient. The company uses a special protocol for this traffic. Branch $i$ has a secret key $k_i$ known only to that branch and to the headquarters. When branch $i$ wants to send a message to branch $j$, branch $i$ first encrypts the message with $k_i$. A courier carries the message from the branch to the headquarters. The headquarters decrypts the message with $k_i$ and encrypts it again with $k_j$. The courier then carries the newly encrypted message to branch $j$, which holds $k_j$. For security reasons the courier can carry only one message at a time.

The distance for delivering one message is therefore the shortest distance from the sending branch to the headquarters plus the shortest distance from the headquarters to the receiving branch, and the distance the courier travels at the end of a month is the sum of the distances of all messages delivered that month.

You are given the road network and the positions of the branches and the headquarters. Consider every way of assigning the subprojects to the branches and find the minimum distance the courier has to travel at the end of a month.

The first line holds four integers $n$, $b$, $s$ and $r$. Here $n$ ($2 \le n \le 5000$) is the number of intersections, $b$ ($1 \le b \le n-1$) is the number of branches, $s$ ($1 \le s \le b$) is the number of subprojects, and $r$ ($1 \le r \le 50000$) is the number of roads. The intersections are numbered from $1$ to $n$. The branches sit at intersections $1$ through $b$, and the headquarters sits at intersection $b+1$.

Each of the next $r$ lines holds three integers $u$, $v$ and $l$. It means there is a road from intersection $u$ to intersection $v$ and its length is $l$ ($1 \le u, v \le n$, $0 \le l \le 10000$). A road can be used only in the given direction. A road from $u$ to $v$ is never given twice, and it is guaranteed that every intersection can reach every other intersection.

Print the minimum distance the courier has to travel.