#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream y("apm.out");
#define N 200001
#define NM 400001
struct muchie{
    int e1,e2,cost;};
muchie g[NM];
int a[N],c[N],n,m;
void init(){
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>g[i].e1>>g[i].e2>>g[i].cost;
    for(i=1;i<=n;i++)
        c[i]=i;}
void sort_muchii(int st,int dr){
    int i,j;
    muchie x;
    if(st<dr){
        x=g[st];
        i=st;
        j=dr;
        while(i<j){
            while(i<j && g[j].cost>=x.cost)
                j--;
            g[i]=g[j];
            while(i<j && g[i].cost<=x.cost)
                i++;
            g[j]=g[i];
        }
        g[i]=x;
        sort_muchii(st,i-1);
        sort_muchii(i+1,dr);
    }
}
int main()
{
    int i,j,min,max,k=0;
    init();
    sort_muchii(1,m);
    for(i=1;k<n-1;i++)
        if(c[g[i].e1]!=c[g[i].e2]){
            a[++k]=i;
            if(c[g[i].e1]<c[g[i].e2]){
                min=c[g[i].e1];
                max=c[g[i].e2];}
            else{
                min=c[g[i].e2];
                max=c[g[i].e1];}
            for(j=1;j<=n;j++)
                if(c[j]==max)
                    c[j]=min;
        }
    int cost1=0;
    for(i=1;i<=n;i++)
        cost1+=g[a[i]].cost;
    y<<cost1<<'\n'<<n-1<<'\n';
    for(i=1;i<n;i++)
        y<<g[a[i]].e1<<" "<<g[a[i]].e2<<'\n';
    return 0;
}