#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include<set>
using namespace std;
ifstream f("apm.in");
ofstream g1("apm.out");
int m,n;
struct muchie
{
    int in,out,cost;
   /* bool operator <(const muchie& pt) const
    {
        return cost<pt.cost;
    }*/
}v[400001];
//vector<muchie> v;
//int *g=new int[n+1]();
//int *hi=new int [n+1]();
int g[200001],hi[200001],x[200001];
bool sortcomp(muchie i,muchie j)
{
    return i.cost<j.cost;
}
void citire()
{
    int i;
    f>>n;
    f>>m;
    for(i=1; i<=m; i++)
        f>>v[i].in>>v[i].out>>v[i].cost;
}
int find(int n)
{
    int k=n,ok,prec;
    while(g[k])
        k=g[k];
    
    ok=k;
   k=n;
    
    while(g[k]){
        prec=k;
        k=g[k];
        g[prec]=ok;
    }
    return ok;
    
}
void R(int p,int q)
{
    if(hi[p]>hi[q]) g[q]=p;
    else
        if(hi[p]<hi[q])
            g[p]=q;
        else
        {
            g[q]=p;
            hi[p]++;
        }

}
int main()
{
    int cs = 0,nr=0,i;
    citire();
    //vector<muchie> x;
    //muchie x[200001];
    sort(v+1,v+m+1,sortcomp);
    for(i=1;i<=m;i++)
    {
        int p=find(v[i].in);
        int q=find(v[i].out);
        if(p!=q)
        {
            cs=cs+v[i].cost;
            x[++nr]=i;
            R(p,q);
            if(nr==n-1) break;
        }
    }
    
    g1<<cs<<endl<<n-1<<endl;
    for(i=1;i<=n-1;i++)
        g1<<v[x[i]].in<<" "<<v[x[i]].out<<endl;
    return 0;
}