#include<fstream>
#include<vector>
#include<algorithm>
#define MMAX 400004
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int x[MMAX],y[MMAX],c[MMAX],ind[MMAX];
int p[MMAX], d[MMAX];

vector<int>edge;


int root(int x)
{
    if (x == p[x])
    {
      return x;
    }

    int root_x = root(p[x]);
    p[x] = root_x;

    return root_x;
}

int verify(int x, int y)
{
  int root_x = root(x);
  int root_y = root(y);

  return (root_x == root_y);
}

void unite(int x, int y)
{
  int root_x = root(x);
  int root_y = root(y);

  if (d[root_x] < d[root_y])
  {
    p[root_x] = root_y;
  }
  else
  {
    p[root_y] = root_x;
  }

  if(d[root_x] == d[root_y])
  {
    d[root_x]++;
  }

}

bool compar(int x, int y)
{
  return (c[x]<c[y]);
}

int main()
{
    int n, m;
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
      fin >> x[i] >> y[i] >> c[i];
      ind[i] = i;

    }

    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        d[i] = 1;
    }

    sort(ind + 1, ind + m + 1, compar);

    int sol = 0;

    for(int i = 1; i <= m; i++)
    {
        if (verify(x[ind[i]], y[ind[i]]) == 0)
           {
             sol += c[ind[i]];
             unite(x[ind[i]], y[ind[i]]);
             edge.push_back(ind[i]);
           }
    }

    fout << sol << "\n";

    fout << n-1 << "\n";

    for (int i = 0; i < n-1; i++)
    {
      fout << x[edge[i]] << " " << y[edge[i]] << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}