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

struct muchie
{
    int a,b;
    int cost;
};

bool operator < (muchie unu,muchie doi )
{
    if(unu.cost< doi.cost)
        return true;
    return false;
}

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

vector <muchie> costuri;
vector <muchie> solutie;
int parinte[200005];
int m,a,b,c;
unsigned n;
long long suma;


int father(int nod)
{
    if(nod==parinte[nod])
        return nod;

    return parinte[nod]=father(parinte[nod]);
}

int main()
{

    fi>>n>>m;

    for(unsigned i=1; i<=n; i++)
        parinte[i]=i;

    for(int i=1; i<=m; i++)
    {
        fi>>a>>b>>c;
        muchie noua;
        noua.a=a;
        noua.b=b;
        noua.cost=c;
        costuri.push_back(noua);

    }

    sort(costuri.begin(),costuri.end());

    for(muchie curent:costuri)
    {
        if( father(curent.a)!=father(curent.b) )
        {
            parinte[father(curent.a)]=father(curent.b);
            suma+=curent.cost;
            solutie.push_back(curent);
        }

        if(solutie.size()==n-1)
            break;
    }

    fo<<suma<<'\n';
    fo<<solutie.size()<<'\n';

    for(muchie x:solutie)
        fo<<x.a<<" "<<x.b<<'\n';

    fi.close();
    fo.close();
    return 0;
}