#include <fstream>
#include <algorithm>

using namespace std;

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

int n, m,nr = 0,val = 0,p = 1;

int daddy[200005], v[400005];

struct muchie
{
    int x,y,z ;
};

muchie bullshit[400005] ;

bool cmp(muchie a,muchie b)
{
    if(a.z <= b.z)
        return true ;
    else
        return false ;
}

int find_daddy(int i)
{
    while( daddy[i] != i )
        i = daddy[i] ;
    return i;
}

bool ver(int a, int b)
{
    if( find_daddy(a) == find_daddy(b) )
        return true;
    else
        return false;
}

void conect(int x, int y,int i)
{
    daddy[find_daddy(y)] = find_daddy(x) ;
    val = val + bullshit[i].z ;
    nr++;
    v[p] = i ;
    p++ ;
}

int main()
{
    in >> n >> m ;
    for(int i=1; i<=n; i++)
    {
        daddy[i] = i ;
    }
    for(int i = 1 ; i<=m ; i++)
    {
        in >> bullshit[i].x >> bullshit[i].y >> bullshit[i].z ;
    }
    sort(bullshit + 1, bullshit + m + 1, cmp);
    for(int i = 1 ; i<=m; i++)
    {
        if( ver(bullshit[i].x,bullshit[i].y) == 0 )
        {
            conect(bullshit[i].x,bullshit[i].y,i);
        }
    }
    out << val << "\n" << nr << "\n" ;
    for(int i=1 ; i<p ; i++)
    {
        out << bullshit[v[i]].x << " " << bullshit[v[i]].y << "\n" ;
    }
    return 0;
}