#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int v[500001]={0};
int dad[500001]={0};

struct arcu{
    int a, b, cost;
}arc[400001]={0};

bool cmp(arcu a1, arcu a2){
    return (a1.cost<a2.cost);
}

int find_dad(int nod){

    if(dad[nod]==0)
        return nod;
    return find_dad(dad[nod]);
}

int main()
{
    int i, j, n, m, op, a, b, ta, tb, cost=0, lg=0;
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(i=1;i<=m;i++){

        f>>arc[i].a>>arc[i].b>>arc[i].cost;
    }
    sort(arc+1, arc+1+m, cmp);

    for(i=1;i<=m;i++)
    {
        ta=find_dad(arc[i].a);
        tb=find_dad(arc[i].b);
        if(ta!=tb)
        {
            cost+=arc[i].cost;
            v[++lg]=i;
            dad[ta]=tb;
            if(lg>=(n-1))
                break;
        }
    }

    g<<cost<<"\n"<<lg<<"\n";
    for(i=1;i<n;i++){
        g<<arc[v[i]].a<<" "<<arc[v[i]].b<<"\n";
    }
}