#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 mergesort(muchie a[],int st, int m, int dr)
{
     int b[200000];
     int i, j, k;
     i = 0; j = st;
     while (j <= m)
        b[i++] = a[j++].c;
     i = 0; k = st;
     while (k < j && j <= dr)
        if (b[i] <= a[j].c)
            a[k++].c = b[i++];
        else
            a[k++].c = a[j++].c;
     while (k < j)
        a[k++].c = b[i++];
}
void merge(muchie a[],int st, int dr)
{
     if (st < dr)
     {
     int m = (st+dr)/2;
     merge(a,st, m);
     merge(a,m+1, dr);
     mergesort(a,st, m, dr);
     }
}


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);
    sortare();
    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;
}