P5633 Minimum Degree-Constrained Spanning Tree.

You are given a weighted undirected graph with $n$ nodes and $m$ edges. You need to find a spanning tree such that the total edge weight is minimized, and the node with index $s$ is connected to exactly $k$ edges.

The first line contains four numbers: $n,m,s,k$. The next $m$ lines each contain three integers: $u,v,w$, meaning there is an edge between $u$ and $v$ with weight $w$.

Output one number: the total edge weight of a spanning tree that satisfies the requirement. There may be cases where no solution exists. If there is no solution, output `Impossible`.

### Constraints For $20\%$ of the testdata, $n \le 10$, $m \le 30$. For $50\%$ of the testdata, $n \le 1000$, $m \le 5000$. For $100\%$ of the testdata, $1\leq s \leq n \le 5\times 10^4$, $1\leq m \le 5\times 10^5 $, $1\leq k \le 100$, $0\leq w\leq 3\times 10^4$. ### Note This problem includes hack testdata (Subtask $2$), worth $0$ points, but if you do not pass the hack testdata, it will not be considered as having passed this problem. Translated by ChatGPT 5