该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在 2077 年的夜之城，整个城市的电力网络由一个 $N \times N$ 的巨型矩阵构成。为了保证供电稳定，市政厅决定建立一套备用连接系统。 矩阵的行编号为 $1 \dots N$，列编号为 $1 \dots N$。 现有 $K$ 个备选方案，第 $i$ 个方案是在坐标 $(r_i, c_i)$ 处建立一个能量核心，花费为 $w_i$。 建立该核心的效果是：将第 $r_i$ 行的电路与第 $c_i$ 列的电路连通。 注意：行与行之间无法直接连接，列与列之间也无法直接连接，必须通过选中的核心作为中介（例如：选中 $(1, 2)$ 和 $(3, 2)$，则第 1 行通过第 2 列与第 3 行连通）。 请问：至少需要花费多少代价，才能使所有的 $N$ 行和 $N$ 列作为一个整体完全连通？如果无法做到，输出 "Impossible"。

输入格式

第一行两个整数 $N, K$，分别表示矩阵大小和备选方案数量。 接下来 $K$ 行，每行三个整数 $r, c, w$，表示在第 $r$ 行第 $c$ 列建立核心的花费为 $w$。

输出格式

输出一个整数，表示最小总花费。若无法连通，输出 Impossible。

输入输出样例 #1

输入 #1

3 5
1 1 10
1 2 5
2 2 5
2 3 10
3 1 5

输出 #1

35

(样例解释：行节点为 R1, R2, R3，列节点为 C1, C2, C3。 选择 (1,2,5) 连通 R1-C2； 选择 (2,2,5) 连通 R2-C2；此时 R1-C2-R2 连通。 选择 (3,1,5) 连通 R3-C1； 还需要连通 {R1,R2,C2} 和 {R3,C1,C3} 集合。 选择 (1,1,10) 连通 R1-C1，此时全部连通。总费 5+5+5+10=25)

数据范围

$1 \le N \le 2000$，$1 \le K \le 50000$，$1 \le w \le 10000$。