CF125E.MST Company

The MST (Meaningless State Team) company won another tender for an important state reform in Berland.

There are n cities in Berland, some pairs of the cities are connected by roads. Each road has its price. One can move along any road in any direction. The MST team should carry out the repair works on some set of roads such that one can get from any city to any other one moving only along the repaired roads. Moreover, this set should contain exactly k capital roads (that is, the roads that start or finish in the capital). The number of the capital is 1.

As the budget has already been approved, the MST Company will profit by finding the set with minimum lengths of roads.

MST（无意义状态团队）公司再次中标了贝尔兰一项重要的国家改革项目。

贝尔兰共有 $n$ 座城市，其中某些城市对之间由道路连接。每条道路都有其价格。道路是双向的，即可以沿任意方向通行。MST 团队需对某组道路进行维修，使得仅通过这些被维修的道路，即可从任意一座城市到达其他任意一座城市。此外，该道路集合中恰好包含 $k$ 条首都道路（即起点或终点为首都的道路）。首都编号为 $1$。

由于预算已获批准，MST 公司将通过寻找总长度最小的满足上述条件的道路集合来实现盈利。

The first input line contains three integers n, m, k (1 ≤ n ≤ 5000;0 ≤ m ≤ 105;0 ≤ k < 5000), where n is the number of cities in the country, m is the number of roads in the country, k is the number of capital roads in the required set. Then m lines enumerate the roads in question. Each road is specified by three numbers a__i, b__i, w__i (1 ≤ a__i, b__i ≤ n; 1 ≤ w ≤ 105), where a__i, b__i are the numbers of cities linked by a road and w__i is its length.

Between each pair of cities no more than one road exists. There are no roads that start and finish in one city. The capital's number is 1.

第一行输入包含三个整数 $n$、$m$、$k$（$1 \leq n \leq 5000$；$0 \leq m \leq 10^5$；$0 \leq k < 5000$），其中 $n$ 表示该国的城市数量，$m$ 表示该国的道路数量，$k$ 表示所要求集合中首都道路的数量。接下来的 $m$ 行列举了这些道路。每条道路由三个数字 $a_i$、$b_i$、$w_i$（$1 \leq a_i, b_i \leq n$；$1 \leq w_i \leq 10^5$）指定，其中 $a_i$、$b_i$ 是由该道路连接的两座城市的编号，$w_i$ 是该道路的长度。

任意两座城市之间至多存在一条道路。不存在起点与终点为同一座城市的道路。首都的城市编号为 $1$。

In the first line print the number of roads in the required set. The second line should contain the numbers of roads included in the sought set. If the sought set does not exist, print -1.

第一行输出所需集合中的道路数量。第二行输出所求集合中包含的道路编号。如果所求集合不存在，则输出 -1。