#include <iostream>
#include <fstream>

using namespace std;

int v[400000][3];
int vlist[400000][2];
int sef[200001];
int temp[200000];

void myqsort(int beginus,int endus){
    int b=beginus,e=endus,pivot=v[(beginus+endus)/2][2],aux;
    while(b<=e){
        while(v[b][2]<pivot) b++;
        while(v[e][2]>pivot) e--;
        if(b<=e){
            aux=v[b][0]; v[b][0]=v[e][0]; v[e][0]=aux;
            aux=v[b][1]; v[b][1]=v[e][1]; v[e][1]=aux;
            aux=v[b][2]; v[b][2]=v[e][2]; v[e][2]=aux;
            b++; e--;
        }
    }
    if(beginus<e) myqsort(beginus,e);
    if(b<endus) myqsort(b,endus);
}

void unionus(int a,int b){
    while(sef[a]!=a)
        a=sef[a];
    while(sef[b]!=b)
        b=sef[b];
    sef[b]=sef[a];
}

int findus(int a,int b){
    int j;
    j=0;
    while(sef[a]!=a){
        temp[j]=a;
        a=sef[a];
        j++;
    }
    j--;
    while(j>=0){
        sef[temp[j]]=a;
        j--;
    }

    j=0;
    while(sef[b]!=b){
        temp[j]=b;
        b=sef[b];
        j++;
    }
    j--;
    while(j>=0){
        sef[temp[j]]=b;
        j--;
    }
    return !(a==b);
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    int n,m;
    fin>>n>>m;

    int i;
    for(i=0;i<m;i++)
        fin>>v[i][0]>>v[i][1]>>v[i][2];

    for(i=1;i<=n;i++)
        sef[i]=i;

    myqsort(0,m-1);

    int nr=0,sum=0,j=0;
    for(i=0;i<m;i++){
        if(findus(v[i][0],v[i][1])){
            unionus(v[i][0],v[i][1]);
            vlist[j][0]=v[i][0];
            vlist[j][1]=v[i][1];
            j++;
            nr++;
            sum+=v[i][2];
        }
    }
    fout<<sum<<"\n"<<nr<<"\n";
    for(i=0;i<j;i++)
        fout<<vlist[i][0]<<" "<<vlist[i][1]<<"\n";
    return 0;
}