#include <iostream>
#include <fstream>
using namespace std;
struct Side{int e1, e2, cost;};
Side Muchii[400005];
int A[200005], c[200005];
int n,m;
void Sortare(int b, int e){
Side x;
int i,j;
if(b<e){
    x=Muchii[b]; i=b; j=e;
    while(i<j){
        while(i<j&&Muchii[j].cost>=x.cost) j--;
        Muchii[i]=Muchii[j];
         while(i<j&&Muchii[i].cost<=x.cost) i++;
        Muchii[j]=Muchii[i];
    }
    Muchii[i]=x;
    Sortare(b,i-1);
    Sortare(i+1,e);
}
}
int main()
{   ifstream fin("apm.in");
     ofstream fout("apm.out");

    int minim, maxim, Nr;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>Muchii[i].e1>>Muchii[i].e2>>Muchii[i].cost;
    for(int i=1; i<=n; i++)
        c[i]=i;
    Sortare(1,m);
    Nr=0;
    for(int i=1; Nr<n-1; i++)
    if(c[Muchii[i].e1]!=c[Muchii[i].e2]){
    A[++Nr]=i;
    if(c[Muchii[i].e1]<c[Muchii[i].e2])
        {minim=c[Muchii[i].e1];
        maxim=c[Muchii[i].e2];
        }
        else {minim=c[Muchii[i].e2];
        maxim=c[Muchii[i].e1];
        }
        for(int j=1;j<=n; j++)
        if(c[j]==maxim) c[j]=minim;
        }
        int cost=0;
        for(int i=1; i<n; i++)
    cost+=Muchii[A[i]].cost;
        fout<<cost<<endl;
        fout<<Nr<<endl;

    for(int i=1; i<n; i++)
  fout<<Muchii[A[i]].e2<<" "<<Muchii[A[i]].e1<<endl;




    return 0;
}