Disconnecting Cities

Chefland consists of $n$ cities numbered $1$, $2$, $\ldots n$. The cities numbered $1$, $2$, $\ldots k$ are special cities. For each unordered pair $i, j$, there exists a bidirectional road, destroying which has a cost of $w_{i, j}$. Find the minimum cost of destroying some subset of roads so that no two special cities have a path between them after the removal of these roads. ### Input There are