#include <iostream>
#include  <fstream>
#include <vector>
#define pb push_back
#define Nmax 400105
#include <algorithm>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int X[Nmax],Y[Nmax],C[Nmax];
int IND[Nmax],GR[Nmax];
int n,m;
int s;
vector<int>raspuns;


bool comparare(int i,int j)
{
    return(C[i]<C[j]);
}


void citire()
{
    fin>>n>>m;

    for(int i=1;i<=m;++i)
    {
        fin>>X[i]>>Y[i]>>C[i];

        IND[i]=i;
    }

    sort(IND+1,IND+m+1,comparare);

    for(int i=1;i<=n;++i)
        GR[i]=i;

    fin.close();
}

int Find(int x)
{

    int r=x;

    while(GR[r]!=r)r=GR[r];

    int y=x;

    while(y!=r)
    {
        int t=GR[y];
        GR[y]=r;
        y=t;
    }

    return r;
}

void uneste(int x, int y)
{
    GR[x]=y;
}

int APM()
{
    int nr=0;

    for(int i=1;i<=m ;++i)
        if(Find(X[IND[i]])!=Find(Y[IND[i]]))
    {  nr++;
         if(nr<=n-1)s+=C[IND[i]];
        uneste(X[IND[i]],Y[IND[i]]);
        raspuns.pb(IND[i]);
    }
    return 0;
}

void afisare()
{  fout<<s<<"\n";
fout<<n-1<<"\n";
    for(int i=0;i<=n-1;++i)
        fout<<X[raspuns[i]]<<" "<<Y[raspuns[i]]<<"\n";
    fout.close();
}
int main()
{
    citire();
    APM();
    afisare();
    return 0;
}