P16825 [AFOI 2025] B.岁月

一年前，你满怀信心走进考场，省队名单好像从未离你这般近过，你也曾在心底暗暗发誓 **“一定要让大家记得我”**。可是**岁月**让你满怀悲痛的走出考场，一年的时光已经过去，**岁月**渐渐磨灭了那悲痛的印记： > **“大家还是忘了我吧”**。 转眼间 NOI 2026 即将到来，小 C 在**岁月**里祝愿各位选手 **“春风得意马蹄疾，一日看尽长安花”！！！** ~~第一个**岁月**指 2025 省选联考 岁月，第二个**岁月**指时间上的**岁月**，第三个**岁月**指本题喵。~~

小 C 有一张 $n$ 个点 $m$ 条边的简单无向连通图 $G=(V,E)$，他想把这张图取下一部分送给小 H。 具体的，他每次想要取下该图的一个非空导出子图 $G[S]$，使得该导出子图形成**森林**，同时剩余部分 $G[V \setminus S]$ 依旧形成了一张**连通图**。 图中的点有**非负**点权，作为节约的好孩子，小 C 还希望每次取下的森林的点权之和最小。请你告诉他，他可以取下的森林的最小点权之和。 :::info[什么是导出子图？什么是森林？] 导出子图指的是由原图顶点的一个子集及连接该子集内顶点的所有边构成的一张原图的子图。 森林指的是每个连通分量（连通块）都是树的图。按照定义，一棵树也是森林。 :::

**本题有多组测试数据。** 第一行输入一个整数 $T$，表示测试数据组数。 接下来依次输入每组测试数据。对于每组测试数据： - 一行，两个整数 $n,m$，表示原图的点数和边数。 - 接下来一行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示点 $i$ 的点权。 - 接下来 $m$ 行，每行 $2$ 个整数 $u,v$ 表示图中的一条无向边。

对于每组测试数据，输出一行一个整数表示答案。

### 样例 $\textbf 1$ 解释 对于第一组测试数据，选择导出子图 $(\{1,2\},\{(1,2)\})$，点权之和为 $517$，且该导出子图是森林剩余部分依旧为连通图。 对于第二组测试数据，选择导出子图 $(\{1\},\{\})$，点权之和为 $0$，且该导出子图是森林剩余部分依旧为连通图。 ### 数据范围 **请注意读入效率对程序效率带来的影响。** 设 $\sum n$ 和 $\sum m$ 分别表示每组数据的 $n,m$ 之和。 对于所有数据： - $1\leq n\leq 10^5$ - $n-1\leq m\leq \min(\frac{n(n-1)}{2},2\times 10^5)$ - $1\leq \sum n\leq 10^6$ - $0\leq \sum m\leq 2\times 10^6$ - $0\leq a_i\leq 10^9$ - $1\leq u_i,v_i\leq n$ - $\forall i,u_i\neq v_i$ - $\forall i\neq j,(u_i,v_i)\neq (u_j,v_j)$。 | 测试点编号 | $n$ | $\max a_i$ | 特殊性质 | | :--------: | :---------: | :---------: | :------: | | $1$ | $\leq 10^5$ | $= 0$ | 无 | | $2\sim 4$ | $\leq 10$ | $\leq 100$ | 无 | | $5\sim 6$ | $\leq 10^5$ | $\leq 10^9$ | $\alpha$ | | $7\sim 10$ | $\leq 10^5$ | $\le10^9$ | 无 | - 特殊性质 $\alpha$：保证 $m=n-1$。