Description

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.

Input Format

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 Format

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.

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

15

Hint

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