#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int sef[200001];
struct muchie{
    int x,y,c;
}m[400001],solutie[400001];
bool cmp(muchie a,muchie b){
    if(a.c<b.c)
        return true;
    return false;
}
int disj(int nod){
    if(sef[nod]==nod)
        return nod;
    else
        return disj(sef[nod]);
}
void unire(int nod1,int nod2){
    int sef1,sef2;
    sef1=disj(nod1);
    sef2=disj(nod2);
    sef[sef2]=sef1;
}
int main()
{
    int N,M;
    int s=0,cost=0;
    cin>>N>>M;
    for(int i=1;i<=M;++i)
        cin>>m[i].x>>m[i].y>>m[i].c;
    sort(m+1,m+M+1,cmp);
   for(int i=1;i<=N;++i)
        sef[i]=i;
    for(int i=1;i<=M;++i)
        if(disj(m[i].x)!=disj(m[i].y)){
            s++;
            solutie[s]=m[i];
            cost+=m[i].c;
            unire(m[i].x,m[i].y);
        }
    cout<<cost<<'\n'<<s<<'\n';
    for(int i=1;i<=s;++i)
                cout<<solutie[i].x<<' '<<solutie[i].y<<'\n';
    return 0;
}