#include <iostream>
#include <fstream>
#include <algorithm>
#define INF 100001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct kt
{
    int pr,ul,val;
}x[200001];
int viz[200001],y[2000001],o;
bool cmp(kt ui,kt uj)
{
    return ui.val<uj.val;

}
int n,p;
int main()
{
    int p,u,i,j,pri,ult,nr=0,ms=0,c=0;
    f>>n>>p;
    for(i=1;i<=n;i++)
    viz[i]=i;
    for(i=1;i<=p;i++)
    {
        f>>x[i].pr>>x[i].ul>>x[i].val;
    }
   sort(x+1,x+p+1,cmp);



    while(ms<n-1)
    {
        do nr++;
        while(viz[x[nr].pr]==viz[x[nr].ul]);
        pri=viz[x[nr].pr];
        ult=viz[x[nr].ul];
        c=c+x[nr].val;
        ms++;
        o++;
        y[o]=nr;
        for(i=1;i<=n;i++)
        if(viz[i]==pri)
        viz[i]=ult;


    }
    g<<c<<"\n"<<o<<"\n";
    for(i=1;i<=o;i++)
        g<<x[y[i]].pr<<" "<<x[y[i]].ul<<"\n";





    return 0;
}