#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[curent.a]=father(curent.b);
            suma+=curent.cost;
            solutie.push_back(curent);
        }

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


fo<<suma<<'\n';
fo<<n-1<<'\n';

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

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