#include <iostream>
#include <fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,s,nr;
struct muchii{
    int x;
    int y;
    int c;
}v[400001],aux;

struct mte{
    int val;
    struct mte *urm;
}*l[200001],*actual,*actualb;

int mt[200001], val[200001];
void qs(int st, int dr){
    int i=st,j=dr;
    int x=v[i+(j-i)/2].c;
    while(i<=j){
        while(i<dr && v[i].c<x)
            ++i;
        while(j>st && v[j].c>x)
            --j;
        if(i<=j){
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
            ++i;
            --j;
        }
    }
    if(st<j)
        qs(st,j);
    if(i<dr)
        qs(i,dr);
}
void kruskal(){
    for(int i=1;i<=n;i++)
        mt[i]=i;//initializez toate nodurile cu prorpia lor multime

    /*for(int i=1;i<=m && nr<n-1;++i)//pana cand nu am n-1 noduri in solutie
        if(mt[v[i].x]!=mt[v[i].y]){//daca apartin multimi diferite
            ++nr;//cresc nr de elem in sol
            val[nr]=i;//marchez nodul ce intra in sol
            s+=v[i].c;//cresc suma
            //determin nodul cu indicele mai mic si mai mare
            int mn,mx;
            if(mt[v[i].x]<mt[v[i].y])
                mn=mt[v[i].x],mx=mt[v[i].y];
            else
                mn=mt[v[i].y],mx=mt[v[i].x];
            //daca un element din mt apartine multimii valorii mai mare
            //ii schimbam valoarea cu cea mai mica
            for(int j=1;j<=n;++j){
                if(mt[j]==mx)
                    mt[j]=mn;
            }
        }*/


    for(int i=1;i<=n;++i){
        actual=new mte;
        actual->val=i;
        actual->urm=l[i];
        l[i]=actual;
    }
    for(int i=1;i<=m && nr<n-1;++i)
        if(mt[v[i].x]!=mt[v[i].y]){
            int mn,mx;
            if(mt[v[i].x]<mt[v[i].y])
                mn=mt[v[i].x],mx=mt[v[i].y];
            else
                mn=mt[v[i].y],mx=mt[v[i].x];
            actual=l[mx];
            while(actual->urm!=NULL){
                mt[actual->val]=mn;
                actual=actual->urm;
            }
            mt[actual->val]=mn;
            actual->urm=l[mn];
            l[mn]=l[mx];
            l[mx]=NULL;
            ++nr;
            s+=v[i].c;
            val[nr]=i;
        }
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;++i)
        in>>v[i].x>>v[i].y>>v[i].c;
    qs(1,m);//sortare
    kruskal();
    out<<s<<"\n"<<nr<<"\n";
    for(int i=1;i<=nr;++i)
        out<<v[val[i]].y<<" "<<v[val[i]].x<<"\n";
    return 0;
}