#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;
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;
    for(int i=1;i<=m && nr<n-1;++i)
        if(mt[v[i].x]!=mt[v[i].y]){
            ++nr;
            val[nr]=i;
            s+=v[i].c;
            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];
            for(int j=1;j<=n;++j){
                if(mt[j]==mx)
                    mt[j]=mn;
            }
        }
}
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);
    kruskal();
    out<<s<<"\n"<<nr<<"\n";
    for(int i=1;i<=nr;++i)
        out<<v[val[i]].x<<" "<<v[val[i]].y<<"\n";
    return 0;
}