//#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct adat
{
    int csp1,csp2,k;
};
vector<adat>x;
vector<long long>v;

vector<pair<long long,long long> > meg;

long long n,m,i,j,k,a,b,c,p,q,sum,db;

int has(adat a,adat b)
{
    if(a.k>b.k) return 0;
    else return 1;
}
int main()
{
    cin>>n>>m;
    x.resize(m+1);
    for(i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        x[i].csp1=a;
        x[i].csp2=b;
        x[i].k=c;
    }

    sort(x.begin()+1,x.end(),has);

    v.resize(n+1);
    for(i=1;i<=n;++i)
        v[i]=i;

    for(i=1;i<=m;++i)
    {
        a=x[i].csp1;
        b=x[i].csp2;
        k=x[i].k;
        p=v[a];
        q=v[b];
        if(q!=p)
        {
            sum+=k;
            for(j=1;j<=n;++j)
            if(v[j]==q) v[j]=p;
            db++;
            meg.push_back({a,b});
        }
        if(db==n-1) break;
    }
    cout<<sum<<"\n"<<meg.size()<<"\n";
    for(i=0;i<meg.size();++i)
        cout<<meg[i].first<<" "<<meg[i].second<<"\n";
    return 0;
}