Reconstructing the Circuit with a Bottleneck Constraint

IY and SY found that the main circuit has been completely destroyed and now must be rebuilt. There are n current‐conducting nodes in the machine room which can be connected with wires. Two nodes that are connected (directly or indirectly) can transfer current.

Due to space restrictions, not all pairs of nodes can be connected. There are m available connections. Each available connection connects two nodes and requires a wire of a given length. However, having only nodes is not enough. SY then takes out her cherished power generator. The generator can only be attached to node s, and it has exactly k interfaces – that is, exactly k wires can be connected to node s. Moreover, for the generator to power the circuit, all its interfaces must be connected.

IY and SY wish to supply power to all nodes. They will select some of the available connections to form a spanning tree T on all n nodes with the following constraints:

1. The tree uses only wires whose lengths do not exceed a threshold L.
2. When the node s is removed from T, the remaining forest has exactly k connected components. Equivalently, in T the degree of node s is exactly k. (Note that no extra wire from node s can be added without forming a cycle.)
3. Among all spanning trees satisfying the above, SY wants the one that minimizes the maximum wire length (i.e. the minimum feasible L).

Once the tree is determined, IY needs two pieces of information:

1. The total wire length required to purchase all the wires used in T (i.e. the sum of the weights of the edges in T).
2. The answer to several queries. Each query gives two nodes u and v, and IY must report the total wire length along the unique path from u to v in T.
</p>

Input and Output Details:

The input begins with four integers: n, m, s and k (1 ≤ s ≤ n). Then follow m lines, each containing three integers u, v and w indicating that node u and node v can be connected by a wire of length w (all available wires are bidirectional). After that, an integer q is given, representing the number of queries. Then q lines follow, each with two integers u and v.

The output should begin with a single integer – the total wire length of the chosen spanning tree. Then output q lines, each containing one integer – the sum of the wire lengths along the path between u and v in the tree T.

Notes:

• All formulas should be typeset in LaTeX. For example, the formula for the generator constraint is: \(\deg(s)=k\).
• You may assume that a valid spanning tree satisfying the constraints always exists.

inputFormat

The first line contains four integers \(n\), \(m\), \(s\) and \(k\) (\(1 \leq s \leq n\)).

The next \(m\) lines each contain three integers \(u\), \(v\) and \(w\) indicating that nodes \(u\) and \(v\) can be connected with a wire of length \(w\).

The following line contains a single integer \(q\) (the number of queries).

Each of the next \(q\) lines contains two integers \(u\) and \(v\), representing a query asking for the total wire length on the unique path between \(u\) and \(v\) in the chosen spanning tree.

outputFormat

On the first line, output the total length of the wires that IY must purchase (i.e. the sum of the weights of the spanning tree \(T\)).

Then output \(q\) lines, each containing one integer – the sum of the wire lengths along the path between the queried nodes in \(T\).

sample

4 5 1 2
1 2 3
1 3 4
2 3 2
2 4 6
3 4 5
2
2 3
4 3

15
5
9

</p>