#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int s[200005];
int sef_s(int nod){
    if(s[nod]==nod)
        return nod;
    return s[nod]=sef_s(s[nod]);
}
struct mch{
    int x;
    int y;
    int c;
    bool operator<(const mch& alt) const{
        return c<alt.c;
    }
};
struct r{
    int x;
    int y;
};
mch v[400005];
r rez[400005];
int main(){
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1);
    for(int i=1;i<=n;i++)
        s[i]=i;
    int ct=0;
    int k=0;
    for(int i=1;i<=m;i++){
        int sx=sef_s(v[i].x);
        int sy=sef_s(v[i].y);
        if(sx!=sy){
            s[sx]=sy;
            ct+=v[i].c;
            k++;
            rez[k].x=v[i].x;
            rez[k].y=v[i].y;
        }
    }
    fout<<ct<<endl<<k<<endl;
    for(int i=1;i<=k;i++)
        fout<<rez[i].y<<" "<<rez[i].x<<endl;
    return 0;
}