Minimum Spanning Tree with Degree Constraint at a Specific Node

You are given an undirected weighted graph with n nodes and m edges. Your task is to find a spanning tree of the graph with the minimum total weight under the additional constraint that the node with index s has exactly k edges incident to it in the tree.

The problem can be formally stated as follows:

Given a graph \(G=(V,E)\) with \(|V|=n\) and \(|E|=m\) where each edge \((u,v)\) has a weight \(w\), find a subset of edges \(T\subseteq E\) such that:

• \(T\) forms a spanning tree (i.e. connects all nodes and contains \(n-1\) edges),
• The total weight \(\sum_{e \in T} w_e\) is minimized, and
• The degree of node \(s\) in \(T\) is exactly \(k\) (i.e., exactly \(k\) edges in \(T\) are incident to \(s\)).

If no such spanning tree exists, you should output -1.

inputFormat

The first line contains four integers \(n\), \(m\), \(s\), and \(k\) (1-based indices), representing the number of nodes, the number of edges, the special node index, and the required degree for node \(s\), respectively.

Each of the following \(m\) lines contains three integers \(u\), \(v\), \(w\), representing an undirected edge between nodes \(u\) and \(v\) with weight \(w\).

outputFormat

Output a single integer representing the minimum total weight of a spanning tree satisfying the condition. If no such spanning tree exists, output -1.

sample

4 4 1 2
1 2 1
1 3 2
2 3 1
3 4 1

4