#include <iostream>
#include <fstream>

using namespace std;
int ind[400001],x[400001],y[400001],c[400001],gr[200001],sol[400001];
void quicksort(int s,int d){
    int x=c[ind[(s+d)/2]];
    int i=s;
    int j=d;
    while(i<=j){
        while(c[ind[i]]<x)i++;
        while(c[ind[j]]>x)j--;
        if(i<=j){
            int a=ind[i];
            ind[i]=ind[j];
            ind[j]=a;
            i++;
            j--;
        }
    }
    if(j>s)quicksort(s,j);
    if(i<d)quicksort(i,d);

}
int grupa(int i){
    if(gr[i]==i)return i;
    gr[i]=grupa(gr[i]);
    return gr[i];
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int i,n,m,k=0,cost=0;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x[i]>>y[i]>>c[i];
        ind[i]=i;}
    for(i=1;i<=n;i++)gr[i]=i;
    quicksort(1,m);
    for(i=1;i<=m;i++){
        if(grupa(x[ind[i]])!=grupa(y[ind[i]])){
            gr[grupa(x[ind[i]])]=grupa(y[ind[i]]);
            k++;
            cost+=c[ind[i]];
            sol[k]=ind[i];}
    }
    g<<cost<<'\n'<<k<<'\n';
    for(i=1;i<=k;i++)g<<x[sol[i]]<<' '<<y[sol[i]]<<'\n';
    return 0;
}