P11729 [集训队互测 2015] Marketing network

“世界充满着各种 if，我们存在着的这个世界也不过是为数众多的 if 的结果中的一个，而未来则更是由于无限的 if 而混沌流动着的世界。” 在某一条世界线中，你可能正在经营一个跨国公司，想想是不是有点激动呢。在那一个世界中，你正被营销网络的设计问题所困扰。 你的跨国公司在 $n$ 个国家设立了销售网点，国家由 $1$ 到 $n$ 编号，这 $n$ 个国家由 $m$ 条双向航线连接。如果把国家看作结点把航线看作边，可以抽象成一个无向图。 你已经在其中的 $S$ 个国家设立了分公司。你会买下一些航线的 VIP 以加速你的商品运输。 无论这条世界线出了什么偏差，你是 OIer 这个事实是不会改变的，所以你对 VIP 航线购买方案有着苛刻的要求： 1. 以任意一个国家作为出发点，都无法只经过 VIP 航线且不经过重复的国家回到出发点。即购买的 VIP 航线形成原图的一个生成森林。 2. 从任意一个分公司出发都可以只经过 VIP 航线到达另一个分公司。 每条航线都有一个权值，表示购买该航线的 VIP 的费用。敏锐的你一定一眼发现了完成目标的最小总花费。但是这样不够任性不够土豪，这势必会影响公司未来的发展。于是机智的你决定求出总费用前 $k$ 小的 VIP 航线购买方案。 两个 VIP 航线购买方案被认为是不同的，当且仅当存在至少一条航线只在其中一个购买方案中被买为 VIP。 “if 只是单纯的 if 罢了。就算有这样一个存在着 good if 的平行世界，人类也不是能简单地跨过世界线，去到那里的。” 但是小小地遐想一下还是很美好的，所以就请你解决这个问题吧。 **简要题意：求出前 $k$ 小的生成森林，要求给定的 $S$ 个点在森林中两两可达。**

第一行，四个正整数 $n, m, S, k$。 第二行，$S$ 个正整数，表示分公司所在的国家，保证读入的国家编号互不相同。 接下来 $m$ 行，每行三个正整数 $u_i，v_i，c_i$，表示国家 $u_i$ 与 $v_i$ 之间有一条费用为 $c_i$ 的航线。保证 $1 \leq u_i, v_i \leq n$，且 $u_i \neq v_i$。

输出 $k$ 行，每行一个正整数，第 $i$ 行的正整数表示总费用第 $i$ 小的 VIP 航线购买方案的总费用。

### 数据范围 除题面样例外的，航线和分公司所在国家均是在 $n, m, S$ 固定的情况下均匀随机生成的。对于所有航线，$c_i$ 是从 $1$ 到 $100$ 的整数中均匀随机选取的。 保证一定存在至少 $k$ 种不同的 VIP 航线购买方案。 （本题洛谷测试点编号较为混乱，下方表格仅作各个测试点范围的大致参考，实际评测中测试点编号与表格无关） | 测试点编号 | $n$ | $m$ | $S$ | $k$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1\sim 5$ | $=10$ | $=20$ | $=4$ | $=10$ | | $6\sim 10$ | $=50$ | $=100$ | $=10$ | $=1$ | | $11\sim 15$ | $=50$ | $=100$ | $=10$ | $=1$ | | $16\sim 20$ | $=50$ | $=100$ | $=5$ | $=20$ | | $21\sim 25$ | $=50$ | $=100$ | $=7$ | $=50$ | | $26\sim 30$ | $=50$ | $=100$ | $=9$ | $=50$ | | $31\sim 35$ | $=50$ | $=100$ | $=10$ | $=50$ | | $36\sim 40$ | $=50$ | $=100$ | $=11$ | $=50$ | | $41\sim 45$ | $=50$ | $=100$ | $=13$ | $=50$ | | $46\sim 50$ | $=50$ | $=100$ | $=15$ | $=50$ |