你好！我是你的OI金牌教练。

我们已经沿着历史长河，学习了图论中的最短路径（Dijkstra）和并查集（集合管理）。

今天，我们将来到疆域辽阔的元朝，结合当时发达的 “站赤（驿站）制度”，来学习图论中另一个极具分量的知识点——最小生成树 (Minimum Spanning Tree, MST)。

这道题在知识点上体现了完美的递进关系：

1. 它利用了之前学过的并查集（秦朝统一）来维护连通性。
2. 它利用了之前学过的贪心思想（排序）。
3. 它区别于最短路径（玄奘西行）：最短路关注的是“点到点”的代价最小，而最小生成树关注的是“让全图连通”的总代价最小。

这是 GESP 6级 乃至 7级 的必考内容，也是 Kruskal 算法的经典应用。

---

第一部分：背景知识讲解

1. 元朝疆域与站赤制度

元朝是中国历史上疆域最辽阔的朝代，“北逾阴山，西极流沙，东尽辽左，南越海表”。 为了有效统治如此庞大的帝国，元世祖忽必烈建立了以大都（今北京）为中心，通往全国乃至境外的驿站制度，蒙语称为**“站赤”**。

2. 修路的代价

要在辽阔的疆土上修筑驿道，连接各个行省和重镇，需要耗费巨大的人力物力。

• 平原地区：修路成本低。
• 崇山峻岭或沙漠戈壁：修路成本极高。

3. 算法模型：最小生成树 (MST)

假设全国有 $N$ 个重要城市。为了保证政令畅通，朝廷希望任意两个城市之间都可以通过驿道互相到达（即图是连通的）。 同时，为了节省国库开支，朝廷希望修路的总成本最低。

• 生成树：在一个图中选出 $N-1$ 条边，将 $N$ 个点连通，且没有环，这叫生成树。
• 最小生成树：在所有可能的生成树中，边权之和最小的那一棵。

---

第二部分：题目内容

题目名称：元朝的驿道 (The Postal Roads of Yuan)

题目描述

元朝疆域辽阔，共有 $N$ 个重要城市，编号为 $1$ 到 $N$。 工部尚书经过勘探，规划出了 $M$ 条可供修筑的备选驿道。第 $i$ 条备选驿道连接城市 $u_i$ 和 $v_i$，修筑成本为 $w_i$。驿道是双向的。

忽必烈下旨，要求从中挑选若干条驿道进行修筑，使得：

1. 全境连通：任意两个城市之间都可以通过修筑的驿道互相到达（可以是间接到达）。
2. 成本最低：所选驿道的修筑成本之和最小。

请你编写程序，计算出达成目标的最小修筑成本。如果利用现有的备选驿道无法将所有城市连通，请输出 impossible。

输入格式

第一行包含两个正整数 $N, M$。

• $N$ 表示城市数量。
• $M$ 表示备选驿道数量。

接下来 $M$ 行，每行包含三个正整数 $u, v, w$。

• 表示城市 $u$ 和 $v$ 之间有一条修筑成本为 $w$ 的备选道路。

输出格式

输出一行。

• 如果能连通所有城市，输出最小总成本。
• 如果不能，输出 impossible。

输入输出样例 #1

输入：

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出：

7

样例 #1 解释：

• 城市：1, 2, 3, 4
• 可选边：(1,2,2), (1,3,2), (1,4,3), (2,3,4), (3,4,3)
• 贪心选择：
  1. 选成本最小的 (1,2) 成本2。联通 {1,2}。
  2. 选成本最小的 (1,3) 成本2。联通 {1,2,3}。
  3. 剩下成本为3的边有 (1,4) 和 (3,4)。随便选一条，比如 (1,4)。联通 {1,2,3,4}。
• 总成本：$2 + 2 + 3 = 7$。

输入输出样例 #2

输入：

3 1
1 2 5

输出：

impossible

样例 #2 解释： 有 3 个城市，但只有一条路连接 1 和 2，城市 3 无法到达，故无法全境连通。

数据范围

对于 $100\%$ 的数据：

• $1 \le N \le 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le w_i \le 10^4$
• 答案可能超过 int 范围，请使用 long long。

---