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

题目背景

John 所居住的城市地铁网络有 $n$ 个站点，部分站点直接有直达地铁线路，不同线路的行驶耗时各不相同。

John 周末要去图书馆自习，需要从家附近的站点出发，换乘地铁到达各个目的地。为了让任意两个站点之间都能换乘到达，同时让整个地铁网络的总行驶时间最短，请你编写一个程序，帮 John 计算出满足条件的最小总时间。

题目描述

给定 $n$ 个地铁站点（编号 $1-n$）和 $m$ 条直达地铁线路，每条线路连接站点 $u$ 和 $v$，行驶时间为 $w$ 分钟。请你选择若干条线路，满足：

1. 所有 $n$ 个站点互相可达（任意两站可通过换乘连通）；
2. 选中的线路的总行驶时间最小；
3. 选中线路无环，且数量恰好为 $n-1$ 条；
4. 若无法满足所有站点联通，输出 $-1$。

输入格式

第一行两个整数 $n,m$ ，表示站点数和直达线路数。
接下来 $m$ 行，每行三个整数 $u,v,w$，表示一条连接 $u$ 和 $v$，行驶时间为 $w$ 的地铁线路。

输出格式

若无法连通所有站点，直接输出 $-1$；
若可以联通所有站点，分两行输出：
第一行输出一个整数，表示满足要求的最小总形式耗时；第二行按站点编号升序输出所有被选中的地铁线路，每条线路格式为 u v （要求 $u<v$，多条线路之间用空格隔开，行末无多余空格）。

输入输出样例

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

3
1 2 1 4 2 3

说明/提示

样例 #1 解释

样例 #1 中，John 可以选中 $(1,2)$、$(1,4)$、$(2,3)$，总耗时 $1+1+1=3$ 分钟。

数据范围与约定

数据保证：

• $1≤n,m≤10$
• $1≤u,v,w≤n$