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

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

struct adat
{
    long long cs1,cs2,k;
};
vector <adat> x;
vector <int> v;
vector <pair<int,int> > y;
long long n,m,i,j,c,p,q,sum,a,b,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);    /// m+1 volt. Te 0-tol (m-1)-ig toltotted fel, igy az m. elem {0,0,0} volt. Ez, amikor rendezted
                    /// bekerult a kozepebe, es az utolso elt nem vette, igy kevesebb jott ki a kelletenel.
    v.resize(n+1);
    for (i=0;i<m;++i)
    {
        cin>>x[i].cs1>>x[i].cs2>>x[i].k;
    }

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

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


   // for (i=0;i<m;++i) cout<<x[i].k<<" "<<x[i].cs1<<" "<<x[i].cs2<<"\n";
    for (i=0;i<m;++i)
    {
        a=x[i].cs1;
        b=x[i].cs2;
        c=x[i].k;
        p=v[a];
        q=v[b];
        if (p!=q)
        {
            y.push_back({a,b});
            sum+=c;
            for (j=1;j<=n;++j)
            {
                if (v[j]==q) v[j]=p;
            }
            db++;
        }
        if (db==n-1) break;
    }

    cout<<sum<<"\n"<<db<<"\n";
    for (auto e:y) cout<<e.first<<" "<<e.second<<"\n";
    return 0;
}