题目描述

给你一个有 $n$ 个节点，$m$ 条边的带权无向图，你需要求得一个生成树，使边权总和最小，且满足编号为 $s$ 的节点正好连了 $k$ 条边。

输入格式

第一行四个数：$n,m,s,k$

下面的 $m$ 行，每行三个整数：$u,v,w$，表示有一条 $u$ 连向 $v$ 权值为 $w$ 的边。

输出格式

输出一个数：满足要求的生成树的总边权。

可能会出现无解的情况，如果无解，则输出 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

提示

数据范围

对于 $20\%$ 的数据，$n \le 10$，$m \le 30$。
对于 $50\%$ 的数据，$n \le 1000$，$m \le 5000$。
对于 $100\%$ 的数据，$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$。

注意

本题设有 hack 数据（Subtask $2$），计 $0$ 分，但若没有通过 hack 数据则不算通过本题。