题目描述

有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少？

输入

$n$（城市数，$1\le n\le100$）

$e$（边数）

以下 $e$ 行，每行3个数$i,j,w_{ij}$，表示在城市$i$,$j$之间修建高速公路的造价（$1\le 造价\le 100$）。

输出

如果无解输出 $-1$，否则按照下面方式输出：

先输出一行一个整数，为最少的造价值。

接下来n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。如果有多个方案，输出任意一个即可。

样例

5 8
1 2 2
2 5 9
5 4 7
4 1 10
1 3 12
4 3 6
5 3 3
2 3 8

19
1 2
5 3
4 3
2 3

来源

一本通在线评测

提示

可能会有重边及自环