背景：

在鳗鱼王国中，长期以来，通过鳗鱼信使进行通信。然而近年来，发明了一种可以瞬间传递声音的魔法线。因此国王决定利用这根魔法线来建立通信网络连接城镇。由于生产魔法线需要时间，所以首先将那些交情深厚的城镇组成小组，只能在小组内进行通信，然后逐渐合并小组，以便在更广阔的范围内进行通信。国王计划了这项策略。现在的问题是，要将属于同一个小组的城镇用魔法线连接起来，需要多长的魔法线。

任务：

给定顶点数为 $N$，边数为 $M$ 的连通无向图 $G$。每个顶点都对应着从 $0$ 到 $N-1$ 的编号。每条边都有一个整数长度。考虑将图G中的顶点分成若干个小组。一开始，假设顶点 $0,1,\dots N-1$ 各自属于自己独立的小组。

给定 $Q$ 个合并查询，每个查询将两个小组合并为一个新的小组。对于每个合并查询，找到使新的小组中的顶点之间连通所需的边集合，使其长度之和最小，并输出该和。