#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;
    }
};
vector<muchie> v;
bool sortcomp(muchie i,muchie j)
{
    return i.cost<j.cost;
}
void citire()
{
    muchie nou;
    int i,j,y,c;
    f>>n;
    f>>m;
    for(i=0; i<m; i++)
    {
        f>>j>>y>>c;
        nou.in=j;
        nou.out=y;
        nou.cost=c;
        v.push_back(nou);
    }
}
int find(int *o,int n)
{
    int k=n,ok,prec;
    while(o[k])
    {
        if(o[k]) k=o[k];
       // o[k]=k;
    }
    ok=k;
   k=n;
    
    while(o[k]){
        prec=k;
        k=o[k];
        o[prec]=ok;
    }
    return ok;
    
}
int main()
{
    int cs = 0;
    citire();
    int *g=new int[n+1]();
    int *hi=new int [n+1]();
    vector<muchie> x;
    sort(v.begin(),v.end(),sortcomp);
    for(muchie i:v)
    {
        int p=find(g,i.in);
        int q=find(g,i.out);
        if(p!=q)
        {
            cs=cs+i.cost;
            //k++;
            if(hi[q]!=hi[p]) g[q]=p;
            else
            if(hi[p]<hi[q])
            g[p]=q;
            else
            {
                g[p]=q;
                hi[q]++;
            }
            x.push_back(i);
        }
    }
    
    g1<<cs<<endl<<n-1<<endl;
    for(muchie i:x)
        g1<<i.in<<" "<<i.out<<endl;
    return 0;
}