#include <bits/stdc++.h>
#define nmax 200005

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

vector <pair <int, pair <int, int> >>muchii;
int tata[nmax], inaltime[nmax];

bool mycmp(pair <int, pair <int, int> > a, pair <int, pair <int, int> > b)
{
    return a.first < b.first;
}

int get_king(int x)
{
    if (tata[x] == x)
        return x;
    tata[x] = get_king(tata[x]);
    return tata[x];
}
int main()
{
   int n, m;
   f >> n >> m;
   for (int i = 1; i <= m; ++ i)
   {
       int x, y, c;
       f >> x >> y >> c;
       muchii.push_back({c, {x, y}});
   }
   for (int i = 1; i <= n; ++ i)
       tata[i] = i;

   sort(muchii.begin(), muchii.end(), mycmp);
   int cost = 0;
   vector <int> ans;

   for (int i = 0; i < muchii.size(); ++ i)
   {
       int a = muchii[i].second.first;
       int b = muchii[i].second.second;
       a = get_king(a);
       b = get_king(b);
       if (a == b)
           continue;
       if (inaltime[a] >= inaltime[b])
           tata[b] = a;
       else
           tata[a] = b;

       if (inaltime[a] == inaltime[b])
           inaltime[a] ++;
       cost += muchii[i].first;
       ans.push_back(i);
   }
  g << cost << '\n' << ans.size() << '\n';
  for (auto i : ans)
      g << muchii[i].second.first << " " << muchii[i].second.second << '\n';
}