#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 200005
using namespace std;

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

int n, m, x[nmax], y[nmax], c[nmax], ind[nmax], gr[nmax], cost=0;
vector<int> mc;

void citeste()
{
    in>>n>>m;
    for (int i=1; i<=m; ++i)
     {
         in>>x[i]>>y[i]>>c[i];
         ind[i]=i;
     }

}

int grupa(int nod)
{
    if ( gr[nod] == nod ) return nod;
    gr[nod] = grupa(gr[nod]);
    return gr[nod];
}

void reuniune(int a, int b)
{
    gr[ grupa(a) ] = grupa(b);
}

bool cmp(int i, int j)
{
    return  ( c[i] < c[j] );
}

int main()
{
    citeste();

    for (int i=1; i<=n; ++i)
     gr[i] = i;

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

    for (int i=1; i<=m; ++i)
     {
         if ( grupa( x[ ind[i] ] ) != grupa( y[ ind[i] ] ) )
          {
              cost += c[ ind[i] ];
              mc.push_back( ind[i] );
              reuniune( x[ind[i] ], y[ ind[i] ] );
          }
     }

     out<<cost<<'\n'<<mc.size()<<'\n';
     for ( int i = 0; i < mc.size(); ++i )
      out<<x[ mc[i] ]<<" "<<y[ mc[i] ]<<'\n';



return 0;
}