#include<iostream>
#include<fstream>

using namespace std;


ifstream f("apm.in");
ofstream out("apm.out");
int m,n,L[200000],temp[200000][2];

struct muchie
{
int x,c,y;
};
muchie u[200000];

void init()
{
    for(int i=1;i<=n;i++)
        L[i]=i;
}

void citire()
{
    int i=0,x,y,c;
    f>>n>>m;
    while(f>>x>>y>>c)
        {
        i++;
        u[i].x=x;
        u[i].y=y;
        u[i].c=c;
        }
f.close();
}

void qSort(muchie vector[],int st,int dr)
{
 int temp,min,max,mijl;

 mijl = vector[st+(dr-st)/2].c;
 min = st; max = dr;
 do
 {
 while(vector[min].c < mijl) min++;
 while(vector[max].c > mijl) max--;
 if(min <= max)
 {
 temp = vector[min].c;
 vector[min++].c = vector[max].c;
 vector[max--].c = temp;
 }
 }while(min <= max); //la fiecare pas sortam "mai bine" intervalul st-dr
 //cand numai avem ce face schimbam intervalul
 if(st < max) qSort(vector,st,max); //crescator
 if(dr > min) qSort(vector,min,dr); //crescator
}


void sortare()
{
    int i,j;
    muchie aux;
    for(i=1;i<m;i++)
        for(j=i+1;j<=m;j++)
            if(u[i].c>u[j].c)
            {
            aux=u[i];
            u[i]=u[j];
            u[j]=aux;
            }
}

int main()
{

    int i=1,j,k=0,x,y,ct=0,z=1;
    citire();
    //merge(u,1,m);
    qSort(u,0,m-1);
    init();
    while(k<n-1)
        {
        if(L[u[i].x]!=L[u[i].y])
            {
            k++;
            ct=ct+u[i].c;
            temp[z][0]=u[i].x;
            temp[z][1]=u[i].y;
            z++;
            x=L[u[i].y];
            y=L[u[i].x];
            for(j=1;j<=n;j++)
                if(L[j]==x)
                    L[j]=y;
            }
        i++;
        }
        out<<ct<<"\n"<<z-1<<"\n";

    for(int i=1;i<z;i++)
        {
        out<<temp[i][0]<<" "<<temp[i][1]<<"\n";
        }

return 0;
}