Problem: 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.

Input

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 ai, bi, wi (1 ≤ ai, bi ≤ n; 1 ≤ w ≤ 105), where ai, bi are the numbers of cities linked by a road and wi 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.

Output

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.

Examples

Input

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


Output

3
1 5 2 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double pi = acos(-1.0);
int dblcmp(double d) {
  if (fabs(d) < eps) return 0;
  return d > eps ? 1 : -1;
}
using namespace std;
const int inf = 0x3f3f3f3f;
int p[5010], r[5010];
void make() {
  memset(r, 0, sizeof(r));
  memset(p, 255, sizeof(p));
}
int find(int x) {
  int px, i;
  for (px = x; p[px] != -1; px = p[px])
    ;
  while (x != px) {
    i = p[x];
    p[x] = px;
    x = i;
  }
  return px;
}
int unio(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return -1;
  if (r[x] > r[y]) {
    p[y] = x;
    return x;
  } else {
    p[x] = y;
    if (r[x] == r[y]) r[y]++;
    return y;
  }
}
struct TT {
  int a, b, v;
  void set(int a, int b, int v) {
    this->a = a;
    this->b = b;
    this->v = v;
  }
  bool operator<(const TT& tt) const { return v < tt.v; }
};
struct Kruskal {
  vector<pair<int, int> > E[5010];
  int result, part;
  vector<pair<int, int> > tree[5010];
  void init() {
    for (int i = 0; i < 5010; i++) E[i].clear();
  }
  void addEdge(int a, int b, int val) {
    E[a].push_back(pair<int, int>(val, b));
    E[b].push_back(pair<int, int>(val, a));
  }
  void kruskal(int n) {
    static TT ee[222222];
    result = 0;
    part = n;
    make();
    for (int i = 0; i < n; i++) tree[i].clear();
    int eNum = 0;
    for (int j = 0; j < n; j++)
      for (vector<pair<int, int> >::iterator i = E[j].begin(); i != E[j].end();
           i++)
        if (i->second > j) ee[eNum++].set(j, i->second, i->first);
    sort(ee, ee + eNum);
    TT e;
    for (int i = 0; i < eNum; i++) {
      e = ee[i];
      if (unio(e.a, e.b) != -1) {
        result += e.v;
        part--;
        tree[e.a].push_back(pair<int, int>(e.v, e.b));
        tree[e.b].push_back(pair<int, int>(e.v, e.a));
      }
    }
  }
};
struct Degree_MST {
  vector<pair<int, int> > E0;
  int v0;
  Kruskal kr;
  vector<pair<int, int> > tmpE0;
  int result;
  int minResult;
  void init(int v0) {
    this->v0 = v0;
    E0.clear();
    kr.init();
  }
  void addEdge(int a, int b, int val) {
    if (a == v0 || b == v0)
      E0.push_back(pair<int, int>(val, a + b - v0));
    else
      kr.addEdge(a, b, val);
  }
  int k_degree_mst(int n, int k) {
    if (E0.size() < k) {
      result = -1;
      return -1;
    }
    kr.kruskal(n);
    tmpE0.clear();
    result = kr.result;
    int part = 0;
    sort(E0.begin(), E0.end());
    for (vector<pair<int, int> >::iterator i = E0.begin(); i != E0.end(); i++) {
      if (unio(v0, i->second) != -1) {
        kr.tree[v0].push_back(pair<int, int>(i->first, i->second));
        kr.tree[i->second].push_back(pair<int, int>(i->first, v0));
        part++;
        result += i->first;
      } else {
        tmpE0.push_back(*i);
      }
    }
    if (part != kr.part - 1 || part > k) return result = minResult = -1;
    minResult = result;
    for (int i = 0; i < k - part; i++) extend_degree();
    return minResult;
  }
  void extend_degree() {
    static bool vis[5010];
    static TT best[5010];
    static queue<int> q;
    memset(best, 255, sizeof(best));
    memset(vis, 0, sizeof(vis));
    q.push(v0);
    vis[v0] = true;
    int u, v, dv;
    while (!q.empty()) {
      u = q.front();
      q.pop();
      for (vector<pair<int, int> >::iterator i = kr.tree[u].begin();
           i != kr.tree[u].end(); i++) {
        dv = i->first;
        v = i->second;
        if (vis[v]) continue;
        vis[v] = true;
        q.push(v);
        if (u != v0) {
          if (best[u].v > dv)
            best[v] = best[u];
          else
            best[v].set(u, v, dv);
        }
      }
    }
    int min = inf;
    pair<int, int> tgt;
    for (vector<pair<int, int> >::iterator i = tmpE0.begin(); i != tmpE0.end();
         i++) {
      if (i->first - best[i->second].v < min) {
        min = i->first - best[i->second].v;
        tgt = *i;
      }
    }
    kr.tree[v0].push_back(pair<int, int>(tgt.first, tgt.second));
    kr.tree[tgt.second].push_back(pair<int, int>(tgt.first, v0));
    TT tt = best[tgt.second];
    kr.tree[tt.a].erase(remove(kr.tree[tt.a].begin(), kr.tree[tt.a].end(),
                               pair<int, int>(tt.v, tt.b)),
                        kr.tree[tt.a].end());
    kr.tree[tt.b].erase(remove(kr.tree[tt.b].begin(), kr.tree[tt.b].end(),
                               pair<int, int>(tt.v, tt.a)),
                        kr.tree[tt.b].end());
    tmpE0.erase(remove(tmpE0.begin(), tmpE0.end(), tgt), tmpE0.end());
    result += tgt.first - tt.v;
    if (result < minResult) minResult = result;
  }
} dm;
map<pair<int, int>, int> idx;
int main() {
  int i, j, k;
  int n, m;
  scanf("%d%d%d", &n, &m, &k);
  dm.init(0);
  for (i = 0; i < m; i++) {
    int q, w, e;
    scanf("%d%d%d", &q, &w, &e);
    q--;
    w--;
    idx[make_pair(q, w)] = i;
    idx[make_pair(w, q)] = i;
    dm.addEdge(q, w, e);
  }
  dm.k_degree_mst(n, k);
  if (k == 0) {
    printf("%d\n", -1 + (n == 1));
    return 0;
  }
  if (dm.result == -1) {
    puts("-1");
    return 0;
  }
  vector<int> ans;
  for (i = 0; i < n; i++) {
    for (j = 0; j < dm.kr.tree[i].size(); j++) {
      int u = i, v = dm.kr.tree[i][j].second;
      ans.push_back(idx[make_pair(u, v)]);
    }
  }
  sort(ans.begin(), ans.end());
  ans.erase(unique(ans.begin(), ans.end()), ans.end());
  printf("%d\n", (int)((ans).size()));
  for (__typeof(ans.begin()) e = ans.begin(); e != ans.end(); ++e) {
    printf("%d\n", (*e) + 1);
  }
  return 0;
}