#include<fstream>
#include<algorithm>
using namespace std;
#define maxm 400010
int n,m,X[maxm],Y[maxm],C[maxm];
int T[200010],ord[maxm],S,sol[maxm];
void citire()
{
    ifstream fin("apm.in");
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>X[i]>>Y[i]>>C[i];
        ord[i]=i;

    }
    for(int i=1;i<=n;i++)
        T[i]=i;
}
int comp_conex(int x)
{
    if(x!=T[x])
        T[x]=comp_conex(T[x]);
    return T[x];
}
bool compar(int i ,int j)
{
    return (C[i]<C[j]);

}
void uneste(int i,int j)
{
    T[comp_conex(i)]=comp_conex(j);
}
int main()
{
    citire();
    ofstream fout("apm.out");
    sort(ord+1,ord+m+1,compar);
    for(int i=1;i<=m;i++)
        if(comp_conex(X[ord[i]])!=comp_conex(Y[ord[i]]))
        {
            S+=C[ord[i]];
            sol[i]=ord[i];
            uneste(X[ord[i]],Y[ord[i]]);
        }
    fout<<S<<'\n';
    fout<<n-1<<'\n';
    for(int i=1;i<=n-1;i++)
        fout<<X[sol[i]]<<" "<<Y[sol[i]]<<'\n';
    return 0;

}