题目描述

城市地图是一张连通的无向图，点表示城市，边的权值表示在两个城市之间建设高速公路的造价。请选择 $n-1$ 条公路，使所有城市直接或间接连通，并使总造价最小。

输入格式

输入先给出城市数 $n$ 和可建设的公路数 $e$。接下来 $e$ 行，每行三个整数 $i,j,w$，表示在城市 $i,j$ 之间修建公路的造价。

输出格式

输出 $n-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

1 2
5 3
4 3
2 3

数据范围

$1\le n\le100$，$n-1\le e\le n(n-1)/2$，$1\le w\le100000$。保证图连通，无自环、重边。