#include <fstream>
#include <queue>
#include <algorithm>
#define N 200000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,i,j,k,V[N],aux,nr,c;
queue <int> Q[N];
struct muchie{
    int start,stop,cost;
}M[2*N],M2[2*N];
bool fcost(muchie a, muchie b){
    return a.cost<b.cost;
}

int main(){
    fin>>n>>m;
    aux=m;
    while(aux)
    {
        aux--;
        fin>>i>>j>>k;
        M[m-aux].start=i;
        M[m-aux].stop=j;
        M[m-aux].cost=k;
    }
    for(i=1;i<=n;i++)
    {
        V[i]=i;
        Q[i].push(i);
    }
    sort(M+1,M+m+1,fcost);
    for(i=1;i<=m;i++)
    {
        if(V[M[i].start]!=V[M[i].stop])
        {
            nr++;
            M2[nr].start=M[i].start;
            M2[nr].stop=M[i].stop;
            c+=M[i].cost;
            k=min(V[M[i].start],V[M[i].stop]);
            j=max(V[M[i].start],V[M[i].stop]);
            aux=V[j];
            while(!Q[aux].empty())
            {
                Q[V[k]].push(Q[aux].front());
                Q[aux].pop();
                V[j]=V[k];
            }
        }
    }
    fout<<c<<'\n'<<nr<<'\n';
    for(i=1;i<=nr;i++)
        fout<<M2[i].start<<" "<<M2[i].stop<<'\n';
    fin.close();
    fout.close();
    return 0;
}