题目描述

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

请你求出总造价最小的方案，并输出需要修建的公路及最小总花费。

输入格式

第一行包含两个整数 $n$ 和 $e$，分别表示城市数和可修建的边数（$1 \le n \le 100$，$1 \le e \le \frac{n(n-1)}{2}$）。

接下来的 $e$ 行，每行包含三个整数 $i, j, w_{ij}$，表示在城市 $i$ 和城市 $j$ 之间修建高速公路的造价 $w_{ij}$（$1 \le w_{ij} \le 10000$）。输入保证任意两个城市之间最多有一条直接边。

输出格式

共 $n$ 行。

前 $n-1$ 行，每行输出两个整数，表示需要修建公路的两个城市编号，按起点编号从小到大输出；若起点相同，按终点编号从小到大输出。

第 $n$ 行输出一个整数，表示最小总花费。

样例

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

1 2
2 3
3 4
3 5
19

样例解释
最小生成树由边 $(1,2)$、$(2,3)$、$(3,4)$、$(3,5)$ 构成，总花费为 $2+8+6+3=19$。输出顺序按要求排列，起点相同时按终点从小到大排列。

数据范围

• $1 < n \le 100$
• $1 \le e \le \frac{n(n-1)}{2}$
• 图为连通图。