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

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int m, el, i, f[200002],c,a,b,j,auxa,auxb ,nr;
long long sum;
pair <int , pair< int, int> > v[400002];
pair <int, int> z[400002];

int calc(int nod)
{
    int aux=nod, a;
    while(f[nod]>0)
        nod=f[nod];
    while(f[aux]>0)
    {
        a=aux;
        aux=f[aux];
        f[a]=aux;
    }
    return nod;
}

int main(){
    fin>>el>>m;
    for(i=1;i<=el;i++)
        f[i]=-1;
    for(i=1;i<=m;i++)
        fin>>v[i].second.first>>v[i].second.second>>v[i].first;
    sort(v+1, v+1+m);
    for(i=1;i<=m;i++)
    {
        a=v[i].second.first;
        b=v[i].second.second;
        auxa=calc(a);
        auxb=calc(b);
        if(auxa!=auxb)
        {
            if(f[auxa]<f[auxb])
            {
                f[auxa]+=f[auxb];
                f[auxb]=auxa;
            }
            else
            {
                f[auxb]+=f[auxa];
                f[auxa]=auxb;
            }
            sum+=v[i].first;
            nr++;
            z[nr].first=v[i].second.first;
            z[nr].second=v[i].second.second;
        }
    }
    fout<<sum<<"\n"<<nr<<"\n";
    for(i=1;i<=nr;i++)
        fout<<z[i].first<<" "<<z[i].second<<"\n";
    fin.close();
    fout.close();
    return 0;
}